poj 1971

题意：给出你一堆坐标点，让你求出这些点组成的平行四边形的个数

思路：求出这些点组成的点组成的线段的重点，如果两条线段的中点相同，则这两条线段组成一个平行四边形。

 

代码如下：

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

struct point 
{
    int x, y;
}p[1001], m[500005];

int cmp(struct point a, struct point b) 
{
    if(a.x == b.x) 
		return a.y < b.y;
    else return a.x < b.x;
}

int main()
{
    int i, j, n, t, cnt, ans;
    for(scanf("%d", &t); t > 0; t--) 
	{
        scanf("%d", &n);
        for(i = 0; i < n; i++) 
		{
            scanf("%d%d", &p[i].x, &p[i].y);
        }
        for(i = 0, cnt = 0; i < n-1; i++) 
		{
            for(j = i+1; j < n; j++) 
			{
                m[cnt].x = p[i].x + p[j].x;
                m[cnt].y = p[i].y + p[j].y;
                cnt += 1;
            }
        }
        sort(m, m+cnt, cmp);
        int tmp = 1;
        for(i = 0, ans = 0; i < cnt-1; i++) 
		{
            if(m[i].x == m[i+1].x && m[i].y == m[i+1].y) 
				tmp++;
            else 
			{
                ans += tmp*(tmp-1)/2;//求出平行四边形的个数
                tmp = 1;        
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}