幾何っぽい問題。確かに数学ゲーではあるのだけど、平行判定は「計算幾何」の知見として習得してしまっても良さそう。
問題概要
二次元平面上に 個の点 () が与えられる。
これらのうちの 3 点であって、同一直線上にあるものが存在するかどうかを判定せよ。
制約
考えたこと
が小さいので、愚直に 通りの場合をすべて全探索すれば OK。
3 点 が一直線上にあるかどうかの判定は次のようにできる。直線 AB と直線 AC が平行かどうかを判定すればよい。
- 直線 AB の方向ベクトルは ( とおく)
- 直線 AC の方向ベクトルは ( とおく)
これらが平行であるための必要十分条件は次のように書ける (高校数学からの知見)。
#include <bits/stdc++.h> using namespace std; bool solve(int N, const vector<int> &x, const vector<int> &y) { for (int i = 0; i < N; ++i) { for (int j = i+1; j < N; ++j) { for (int k = j+1; k < N; ++k) { int dx1 = x[k] - x[i], dy1 = y[k] - y[i]; int dx2 = x[j] - x[i], dy2 = y[j] - y[i]; if (dx1 * dy2 == dx2 * dy1) return true; } } } return false; } int main() { int N; cin >> N; vector<int> x(N), y(N); for (int i = 0; i < N; ++i) cin >> x[i] >> y[i]; if (solve(N, x, y)) cout << "Yes" << endl; else cout << "No" << endl; }