POJ 1971 统计平行四边形 HASH

题目链接：http://poj.org/problem?id=1971

题意：给定n个坐标。问有多少种方法可以组成平行四边形。题目保证不会有4个点共线的情况。

思路：可以发现平行四边形的一个特点，就是对角线相交后得到的点。如果两点线的中点相交，那么这两条线就可以组成一个平行四边形[不需去排除4点共线]，所以枚举两两组合的点对HASH成中点。然后判断所有中点，如果某个中点出现了K次，那么可以组成K*(K-1)/2个平行四边形。 用map来判断某个中点出现次数会TLE，所以可以对中点进行排序后判重复次数。

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<string>

#include<vector>

#include<cmath>

#include<map>

using namespace std;

typedef long long int LL;

typedef unsigned int uint;

#define mp(x,y) make_pair(x,y)

const int MAXN=+;

struct Point{

    double x,y;

    Point(double a=,double b=):x(a),y(b){};

};

Point P[MAXN],MP[MAXN*MAXN];

Point MidP(Point a,Point b){

    return Point((a.x+b.x)/,(a.y+b.y)/);

}

bool cmp(Point a,Point b){

    if(a.x==b.x){

        return a.y<b.y;

    }

    return a.x<b.x;

}

int main(){

#ifdef kirito

    freopen("in.txt","r",stdin);

    freopen("out.txt","w",stdout);

#endif

    int n,t;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        int ans=,cnt=;

        for(int i=;i<n;i++){

            scanf("%lf %lf",&P[i].x,&P[i].y);

        }

        for(int i=;i<n;i++){

            for(int j=i+;j<n;j++){

                Point midP=MidP(P[i],P[j]);

                MP[cnt++]=midP;

            }

        }

        sort(MP,MP+cnt,cmp);

        int idx=,tmp=;

        for(int i=;i<cnt;i++){

            if(MP[i].x==MP[idx].x&&MP[i].y==MP[idx].y){

                tmp++;

            }

            else{

                ans+=tmp*(tmp-)/;

                idx=i; tmp=;

            }

        }

        ans+=tmp*(tmp-)/;

        printf("%d\n",ans);

    }

    return ;

}