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;
}

Download