Official

C - Collinearity Editorial by tatyam


\(N ≤ 10^2\) なので、 \(3\) 点が同一直線上にあるかを高速に判定できれば、全ての \(3\) 点の選び方について同一直線上にあるか判定することで AC できます。

\(1\) つの点が原点になるように \(3\) 点を平行移動しておきます。
3 点 \(A(0, 0), B(x_1, y_1), C(x_2, y_2)\) が同一直線上にあるかは、\(AB\)\(AC\) の傾きが等しいかで判定できます。

\(\dfrac{y_1}{x_1}=\dfrac{y_2}{x_2}\) で判定すると \(0\) 除算が発生するため、両辺に \(x_1x_2\) を掛けて、 \(x_2y_1=x_1y_2\) で判定すると良いでしょう。

\(1\) 回の判定は \(O(1)\) でできるので、全体で \(O(N^3)\) で解くことができます。

回答例 (Python)

n = int(input())
p = [tuple(map(int, input().split())) for i in range(n)]

for i in range(n):
    for j in range(i):
        for k in range(j):
            x1, y1 = p[i]
            x2, y2 = p[j]
            x3, y3 = p[k]
            x1 -= x3
            x2 -= x3
            y1 -= y3
            y2 -= y3
            if x1 * y2 == x2 * y1:
                print("Yes")
                exit()

print("No")

回答例 (C++)

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

int main(){
    int n;
    cin >> n;
    vector<pair<int, int>> p(n);
    for(auto& [x, y] : p) cin >> x >> y;
    for(int i = n; i--; ) for(int j = i; j--; ) for(int k = j; k--; ){
        auto [x1, y1] = p[i];
        auto [x2, y2] = p[j];
        auto [x3, y3] = p[k];
        x1 -= x3;
        x2 -= x3;
        y1 -= y3;
        y2 -= y3;
        if(x1 * y2 == x2 * y1){
            puts("Yes");
            return 0;
        }
    }
    puts("No");
}

posted:
last update: