POJ 1971-Parallelogram Counting,暴力1063ms！

刚学hash还不会用，看到5000ms的时限于是想着暴力来一发应该可以过。以前做过类似的题，求平行四边形个数，好像是在CF上做的，但忘了时限是多少了，方法是一样的。

题意：给出n个点坐标，求平面中有多少个平行四边形。

思路：我们知道，平行四边形的条件是两条边平行且相等。我们把每条边分解成x和y方向的向量，只要两条边对应相等就可以了，于是预处理所有的边，然后排序，然后相等的肯定在一起，所以用试探法往前，注意每个平形四边形都被记录了两次，所以答案是总数量除以2。

struct line

{

    int x,y,i,j;

} a[N*N];

struct node

{

    int x,y;

} p[N];

int cmp(node a,node b)

{

    if(a.x!=b.x) return a.x<b.x;

    return a.y<b.y;

}

int cmp1(line a,line b)

{

    if(a.x!=b.x) return a.x<b.x;

    return a.y<b.y;

}

int main()

{

    int t,n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%d",&n);

        for(int i=0; i<n; i++) scanf("%d%d",&p[i].x,&p[i].y);

        sort(p,p+n,cmp);

        int len=0;

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

            for(int j=n-1; j>i; j--)

            {

                a[len].i=i,a[len].j=j;

                a[len].x=p[j].x-p[i].x,a[len++].y=p[j].y-p[i].y;

            }

        sort(a,a+len,cmp1);

        int ans=0;

        for(int i=0; i<len; i++)

        {

            for(int j=i+1; j<len; j++)

                if(a[i].x==a[j].x&&a[i].y==a[j].y)

                {

                    if(a[i].i!=a[j].i&&a[i].i!=a[j].j&&a[i].j!=a[j].i&&a[i].j!=a[j].j)

                        ans++;

                }

                else break;//往后没有必要了，不然超时

        }

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

    }

    return 0;

}

巴特西

POJ 1971-Parallelogram Counting,暴力1063ms！

最新文章

热门文章