[AtCoder] ABC 181 C – Collinearity

2020年11月1日2020年12月12日

問題

方針

点 \( A, B , C \) が順序を問わずに一直線上にある条件は、

\[ \overrightarrow{AB}  = t \overrightarrow{AC}  \]

を満たす \( t \) が存在することです。ここで、\( \overrightarrow{AB} = (x_1, y_1) \), \( \overrightarrow{AC} = (x_2, y_2) \)  とすると、\( t \) が存在する条件は、

\[ x_1y_2 – x_2y_1 = 0\]

です。したがって、\( 3 \) 点を全探索します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int N;
    cin >> N;
    int x[N], y[N];
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
    }
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            for (int k = j + 1; k < N; k++) {
                int x1 = x[j] - x[i];
                int y1 = y[j] - y[i];
                int x2 = x[k] - x[i];
                int y2 = y[k] - y[i];
                if (x1 * y2 - x2 * y1 == 0) {
                    cout << "Yes\n";
                    return 0;
                }
            }
        }
    }
    cout << "No\n";
    return 0;
}

参考