問題概要

二次元平面上に $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;
}

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

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

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

問題概要

制約

考えたこと