poj2002 Squares(hash+折半枚举)

Description

A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles. It is also a polygon such that rotating about its centre by 90 degrees gives the same polygon. It is not the only polygon with the latter property, however, as a regular octagon also has this property.

So we all know what a square looks like, but can we find all possible squares that can be formed from a set of stars in a night sky? To make the problem easier, we will assume that the night sky is a 2-dimensional plane, and each star is specified by its x and y coordinates.

Input

The input consists of a number of test cases. Each test case starts with the integer n (1 <= n <= 1000) indicating the number of points to follow. Each of the next n lines specify the x and y coordinates (two integers) of each point. You may assume that the points are distinct and the magnitudes of the coordinates are less than 20000. The input is terminated when n = 0.

Output

For each test case, print on a line the number of squares one can form from the given stars.

Sample Input

Sample Output

1

6

1
题意：在二维平面上，给你n个点的坐标，求任取四点构成正方形的个数
题解：好吧，暴力O(n^4)又t了……
那么折半枚举吧
枚举两个点连成一条线，然后根据这条线可以得到正方形的另外两个点，根据hash可以快速确定点是否在n个点中，即可以计算出正方形的个数
代码如下：

#include<map>

#include<vector>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x3f3f3f3f

using namespace std;

struct node

{

    int x,y;

} a[];

vector<long long> g[];

int n;

int cmp(node x,node y)

{

    if(x.x==y.x)

    {

        return x.y<y.y;

    }

    return x.x<y.x;

}

int main()

{

    while(scanf("%d",&n)==&&n)

    {

        int ans=;

        vector<long long> g[];

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

        {

            scanf("%d%d",&a[i].x,&a[i].y);

        }

        sort(a+,a+n+,cmp);

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

        {

            long long key=(a[i].x*a[i].x+a[i].y*a[i].y)%;

            g[key].push_back(i);

        }

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

        {

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

            {

                int x1,y1,x2,y2;

                int dx=(a[j].x-a[i].x),dy=(a[j].y-a[i].y);

//            if(dx<0||dy<0)

//            {

//                continue;

//            }

                x1=a[i].x-dy;

                y1=a[i].y+dx;

                x2=a[j].x-dy;

                y2=a[j].y+dx;

                int flag=;

                long long key=(x1*x1+y1*y1)%;

                for(int k=; k<g[key].size(); k++)

                {

                    if(a[g[key][k]].x==x1&&a[g[key][k]].y==y1)

                    {

                        flag+=;

                    }

                }

                key=(x2*x2+y2*y2)%;

                for(int k=; k<g[key].size(); k++)

                {

                    if(a[g[key][k]].x==x2&&a[g[key][k]].y==y2)

                    {

                        flag+=;

                    }

                }

                if(flag==)

                {

//                if(a[i].x==x1&&a[i].y==y1||a[j].x==x2&&a[j].y==y2||a[i].x==x2&&a[i].y==y2||a[j].x==x1&&a[j].y==y1)

//                {

//                    continue;

//                }

//                printf("%d %d\n",dx,dy);

//                printf("%d %d %d %d %d %d %d %d\n",a[i].x,a[i].y,a[j].x,a[j].y,x1,y1,x2,y2);

                    ans++;

                }

            }

        }

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

    }

}

巴特西

poj2002 Squares(hash+折半枚举)

最新文章

热门文章