題目大意:給你一個(gè)二維平面上面的n（1000）個(gè)點(diǎn)的坐標(biāo)（每個(gè)點(diǎn)坐標(biāo)都不超過(guò)20000），讓你找出有多少個(gè)正方形。給了三秒半····思路：還是先看一眼暴力枚舉，4個(gè)點(diǎn)的所有可能組合為n^4肯定超時(shí)了。枚舉每?jī)蓚€(gè)點(diǎn)的組合O(n^2)，然后看是否存在可以和他們組成正方形的點(diǎn)。即該位置上是否有點(diǎn)（用哈希表可以將查找過(guò)程時(shí)間復(fù)雜度降為O(1)。

這個(gè)哈希真是猛，只是要根據(jù)經(jīng)驗(yàn)找個(gè)合適的哈希函數(shù)，一定要讓哈希函數(shù)的值分布均勻，不然的話，和就相當(dāng)于還是在枚舉。這道題原本MOD為1000的時(shí)候3438ms險(xiǎn)過(guò)。MOD改為10000之后，速度瞬間變快只需2469ms用空間換時(shí)間很劃算。程序跑快快~

#include<iostream>#include<string.h>#include<stdio.h>#define N 1050#define MOD 10000using namespace std;int n;struct point{	int x;int y;}poi[N];int hash[MOD+10]={0};int next[MOD+10]={0};void input(){	for(int i=1;i<=n;i++)	{		scanf("%d%d",&poi[i].x,&poi[i].y);		int x;		x=(poi[i].x*poi[i].x+poi[i].y*poi[i].y)%MOD+1;		next[i]=hash[x];		hash[x]=i;	}}bool find(point x){	int u=(x.x*x.x+x.y*x.y)%MOD+1;	u=hash[u];	while(u)	{		if(poi[u].x==x.x&&poi[u].y==x.y)return 1;		u=next[u];	}	return 0;}void init(){	memset(hash,0,sizeof(hash));	memset(next,0,sizeof(next));}int main(){	while(cin>>n)	{		if(n==0)break;		input();		int s=0;		for(int i=1;i<=n;i++)		{			for(int j=1;j<=n;j++)			{				if(i==j)continue;				int x=poi[i].x-poi[j].x;				int y=poi[i].y-poi[j].y;				point p,q;				p.x=poi[i].x-y;				p.y=poi[i].y+x;				q.x=poi[j].x-y;				q.y=poi[j].y+x;				if(find(p)&&find(q))s++;				p.x=poi[i].x+y;				p.y=poi[i].y-x;				q.x=poi[j].x+y;				q.y=poi[j].y-x;				if(find(p)&&find(q))s++;			}		}		s=s/8;		cout<<s<<endl;		init();	}	}