Official

C - Collinearity Editorial by evima


Since \(N ≤ 10^2\), if you can judge whether three points are on the same line, you can get AC by inspecting all combinations of three points.

Let’s apply parallel translation to the three points so that one of them is at the origin. In order to check if three points, \(A(0, 0), B(x_1, y_1)\) and \(C(x_2, y_2)\) are in the same line, one can check if \(AB\) and \(AC\) have the same slope.

If you use \(\dfrac{y_1}{x_1}=\dfrac{y_2}{x_2}\), division-by-zero may occur, so it is good to multiply both sides by \(x_1x_2\) and use \(x_2y_1=x_1y_2\).

Since an operation for a combination can be performed in a \(O(1)\) time, the problem can be solved in a total of \(O(N^3)\) time.

Sample Code (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")

Sample Code (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: