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: