けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 181 C - Collinearity (灰色, 300 点)

幾何っぽい問題。確かに数学ゲーではあるのだけど、平行判定は「計算幾何」の知見として習得してしまっても良さそう。

問題概要

二次元平面上に  N 個の点 ( (x_{i}, y_{i})) が与えられる。

これらのうちの 3 点であって、同一直線上にあるものが存在するかどうかを判定せよ。

制約

  •  3 \le N \le 100

考えたこと

 N が小さいので、愚直に  {}_{N}{\rm C}_{3} 通りの場合をすべて全探索すれば OK。

3 点  A(a_{x}, a_{y}), B(b_{x}, b_{y}), C(c_{x}, c_{y}) が一直線上にあるかどうかの判定は次のようにできる。直線 AB と直線 AC が平行かどうかを判定すればよい。

  • 直線 AB の方向ベクトルは  (b_{x}-a_{x}, b_{y}-a_{y}) ( = (d_{1x}, d_{1y}) とおく)
  • 直線 AC の方向ベクトルは  (c_{x}-a_{x}, c_{y}-a_{y}) ( = (d_{2x}, d_{2y}) とおく)

これらが平行であるための必要十分条件は次のように書ける (高校数学からの知見)。

 d_{1x} \times d_{2y} = d_{2x} \times d_{1y}

#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;
}