2214.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2214 on 2006-04-26 at 12:22:30 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int PN = 1024;
const int EN = 1 << 19;

int x[PN], y[PN];

class Edge {
public:
	int mx, my, dx, dy;
	void set(int, int);
	bool operator <(const Edge&) const;
	bool ce(const Edge&) const;
	bool ke(const Edge&) const;
};
void Edge::set(int b, int e) {
	mx = x[b]+x[e], my = y[b]+y[e];
	dx = x[e]-x[b]; dy = y[e]-y[b];
	if(dx < 0) dx = -dx, dy = -dy;
	else if(dx == 0) dy = abs(dy);
}
bool Edge::operator <(const Edge& e) const {
	if(mx != e.mx) return mx < e.mx;
	else if(my != e.my) return my < e.my;
	else return dy*e.dx < dx*e.dy;
}
bool Edge::ce(const Edge& e) const {
	return mx == e.mx && my == e.my;
}
bool Edge::ke(const Edge& e) const {
	return dy*e.dx == dx*e.dy;
}

Edge e[EN];

int main()
{
	int t, T, i, j;

	scanf("%d", &T);
	for(t = 0; t < T; t++) {
		int n; scanf("%d", &n);
		for(i = 0; i < n; i++) scanf("%d %d", &x[i], &y[i]);
		int en = 0;
		for(i = 0; i < n; i++)
			for(j = i+1; j < n; j++) e[en++].set(i, j);
		sort(e, e+en);
		int total = 0, ke = 0, kbe = 0;
		for(i = 0; i <= en; i++, ke++)
			if(i == 0 || i == en || !e[i].ce(e[i-1])) {
				total += kbe*(ke-kbe);
				ke = 0; kbe = 1;
			} else if(e[i].ke(e[i-1])) kbe++;
			else {
				total += kbe*(ke-kbe);
				kbe = 1;
			}
		printf("%d\n", total);
	}
	
	return 0;
}