QBPOINT - Bộ ba điểm thẳng hàng

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
const int N = 2002;
using namespace std;
int n, res;
ii vt[N], a[N];

ii reduce(int x, int y) {
    //toi gian vector (x, y)
    int g = __gcd(x, y);
    x /= g; y /= g;
    if (x < 0) {x = -x; y = -y;}
    return ii(x, y);
}

int main()
{
    scanf("%d", &n);
    int i, j, k, m;
    for(i = 1; i <= n; i++) scanf("%d %d", &a[i].X, &a[i].Y);
    for(i = 1; i < n; i++) {
        m = 0;
        for(j = i + 1; j <= n; j++)
            vt[m++] = reduce(a[i].X - a[j].X, a[i].Y - a[j].Y);
        sort(vt, vt + m);
        for(j = 0; j < m; j = k) {
            k = j;
            while (k < m && vt[k] == vt[j]) k++;
            res += (k - j) * (k - j - 1) / 2;
        }
    }
    printf("%d", res);
    return 0;
}

Download