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

Tác giả: happyboy99x

Ngôn ngữ: C++

#include<cstdio>
#include<algorithm>
using namespace std;

#define N 2000
long long sqr(const int &x) { return (long long) x * x; }

struct Point {
	int x, y;
	void read() {
		scanf("%d%d", &x, &y);
	}
} p[N];

struct Vector {
	int x, y;
	Vector() {}
	Vector(const Point &A, const Point &B) {
		int tx = B.x - A.x, ty = B.y - A.y;
		if(ty < 0 || ty == 0 && tx < 0) { ty = -ty; tx = -tx; }
		x = tx; y = ty;
	}
	inline bool operator < (const Vector &o) const {
		return x * o.y - y * o.x > 0;
	}
	inline bool operator == (const Vector &o) const {
		return x * o.y == y * o.x;
	}
	inline bool operator != (const Vector &o) const {
		return x * o.y != y * o.x;
	}
} u[N];

int main() {
#ifdef __DONGOCKHANH__
	freopen("input.txt", "r", stdin);
#endif
	int n; scanf("%d", &n);
	for(int i = 0; i < n; p[i++].read());
	int res = 0;
	for(int i = 0; i < n; ++i) {
		for(int j = i + 1; j < n; ++j) u[j] = Vector(p[i], p[j]);
		sort(u+i+1, u+n); int begin = i+1;
		for(int j = i + 1; j < n; ++j) if(u[j] != u[begin]) {
			res += (j - begin) * (j - begin - 1) / 2;
			begin = j;
		}
		res += (n - begin) * (n - begin - 1) / 2;
	}
	printf("%d\n", res);
	return 0;
}

Download