Poj 2002 Squares (正方形个数 Hash)

比眉伴天荒 2022-08-25 15:55 116阅读 0赞

题意：平面内一堆点，问其中有多少个正方形，相同的四个点，不同顺序构成的正方形视为同一正方形。

思路：设两个点的坐标为(a1,a2),(b1,b2),若构成正方形，另两个点的坐标是：(a1-(a2-b2), a2+(a1-b1))、(b1-(a2-b2), b2+(a1-b1)))或者：(a1-(a2-b2), a2+(a1-b1))、(b1-(a2-b2), b2+(a1-b1))，注意这样处理之后每个正方形都被数了4次。

枚举2点，另两个点的快速查找用Hash实现。貌似我这个Hash函数效率比较低。

#include <cstdio>
    #include <cstring>
    
    const int prime=1999;
    
    struct Node 
    {
    	int x,y,next;
    }node[1005];
    
    int n,e;
    int head[3000],data[1005][2];
    
    void Insert (int key,int x,int y)
    {
    	node[e].x=x;
    	node[e].y=y;
    	node[e].next=head[key];
    	head[key]=e++;
    }
    
    bool check (int key,int x,int y)
    {
    	for (int i=head[key];i!=-1;i=node[i].next)
    		if (node[i].x==x && node[i].y==y)
    			return true;
    	return false;
    }
    
    int Deal ()
    {
    	int ans=0;
    	for (int i=1;i<n;i++)
    		for (int j=i+1;j<=n;j++)
    		{
    			int A=data[j][1]-data[i][1];
    			int B=data[j][0]-data[i][0];
    
    			int x1=data[i][0]+A;
    			int y1=data[i][1]-B;
    			int x2=data[j][0]+A;
    			int y2=data[j][1]-B;
    			int x=(x1+y1+40000)%prime;
    			int y=(x2+y2+40000)%prime;
    			if (check(x,x1,y1) && check(y,x2,y2))
    				ans++;
    
    			x1=data[i][0]-A;y1=data[i][1]+B;
    			x2=data[j][0]-A;y2=data[j][1]+B;
    			x=(x1+y1+40000)%prime;
    			y=(x2+y2+40000)%prime;
    			if (check(x,x1,y1) && check(y,x2,y2))
    				ans++;
    		}
    	return ans/4;
    }
    
    int main ()
    {
    	while (scanf("%d",&n),n)
    	{
    		e=0;
    		memset(head,-1,sizeof(head));
    		for (int i=1;i<=n;i++)
    		{
    			scanf("%d%d",&data[i][0],&data[i][1]);
    			//hash函数也可以用 key = (x^2+y^2)%prime
    			int tmp=(data[i][0]+data[i][1]+40000)%prime;
    			Insert(tmp,data[i][0],data[i][1]);
    		}
    		printf("%d\n",Deal());
    	}
    	return 0;
    }