poj 1971 Parallelogram Counting 平行四边形个数

题目描述：http://poj.org/problem?id=1971

// 该题关键是如何判定给定4点可否构成平行四边形
// 根据平行四边形对角线互相平分，可知该题中只要
// 两对顶点连线的中点重合，就可以构成平行四边形（？？？），
// 因为不存在4点共线
// 发现poj的测试数据不完善
// 在最后统计平行四边形个数的时候
// 如果不考虑 i == k + 2 这种情况也可以通过


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

struct point {
	int x,y;
};

/* bool comp(point a, point b) {
	if(a.x == b.x)
		return a.y < b.y;
	return a.y < b.y;
} */
bool operator<(const point a,const point one) { 
	if(a.x == one.x)    
		return a.y<one.y; 
	return a.x<one.x;
}

int main() {
	point dots[1005];
	point mid[500000];
	int nCase;
	scanf("%d", &nCase);
	while(nCase--) {
		int k = 0;
		int n;
		scanf("%d", &n);
		for(int i = 0; i < n; i++)
			scanf("%d %d", &dots[i].x, &dots[i].y);
		for(int i = 0; i < n; i++)
			for(int j = i + 1; j < n; j++) {
				mid[k].x = (dots[i].x + dots[j].x);
				mid[k].y = (dots[i].y + dots[j].y);
				k++;
			}
		sort(mid, mid + k);  //默认调用重载运算符operator< 或者加上第三个参数comp(注释部分函数)
		int sum = 0;
		int count = 1;
		for(int i = 0; i < k - 1; i++) {
			if(mid[i].x == mid[i + 1].x && 
			   mid[i].y == mid[i + 1].y)
			   count++;
			else {
				sum += count * (count - 1) / 2;
				count = 1;
			}
			//当mid数组最后几个点(设为p)相同时，应把k*(k-1)/2加到sum中，以上else并未作处理
			//未考虑这种情况也能通过，可能是测试数据不足
			if(i == k - 2)   
				sum += (count - 1) * count / 2;
		}
		printf("%d\n", sum);
	}
	return 0;
}