QBPOINT - Bộ ba điểm thẳng hàng
Tác giả: khuc_tuan
Ngôn ngữ: C++
#include <iostream>
using namespace std;
struct Point {
int x, y;
};
struct Frac {
int a, b;
};
int n, nf;
Point a[2020];
Frac f[2020];
bool cmp(Frac a, Frac b) {
return a.a*b.b < a.b*b.a;
}
int main() {
scanf("%d", &n);
for(int i=0;i<n;++i) scanf("%d%d", &a[i].x, &a[i].y);
unsigned int total = 0;
for(int i=0;i<n;++i) {
Point p = a[i];
int ngang = 0;
nf = 0;
for(int j=i+1;j<n;++j) if(i!=j) {
if(a[j].y==p.y) ++ ngang;
// else if(a[j].x==p.x) ++ doc;
else {
int dy = a[j].y - p.y;
int dx = a[j].x - p.x;
if(dy<0) {
dy = -dy;
dx = -dx;
}
f[nf].a = dx;
f[nf].b = dy;
++nf;
}
}
total += ngang * (ngang-1) / 2;
sort(f,f+nf,cmp);
int c = 0;
for(int j=0;j<nf;++j)
if(j==0) c = 1;
else if(f[j].a*f[j-1].b==f[j].b*f[j-1].a) ++c;
else {
total += c * (c-1) / 2;
c = 1;
}
total += c * (c-1) / 2;
}
cout << total << endl;
return 0;
}