经典好题。
题意是要我们找出所有的正方形。1000点，只有枚举咯。
如图，如果我们知道了正方形A，B的坐标，便可以推测出C，D两点的坐标。反之，遍历所有点作为A，B点，看C，D点是否存在。存在的话正方形数+1。
假设A点坐标为(x1,y1)，B点坐标为(x2，y2)，则根据三角形全等，易知
C点坐标：( x1+(y2-y1),y1-(x2-x1) )
D点坐标：( x2+(y2-y1),y2-(x2-x1) )
当然，如果我们遍历任意两个点，一个正方形将会被计数四次（四条边）。我们可以只判断斜率>=0的边，这条边在正方形的上方（如图AB边），这样不用重复验证四次了。
过程搞清楚了，下面要解决的就是如何判断C，D点是否存在了。
最简单的办法，直接使用set。我们把出现的点加到set里，判断时用find函数即可。当然，时效比较差。笔者测试是1000MS+。
而后，我们也可以使用二分查找。
当然，最快还是hash了。hash分为两种，开放寻址和链式，来解决冲突。在网上搜了很多解题报告，发现大家很多把链式叫做开放寻址……百度百科上有说明，大家可以看一下：http://baike.baidu.com/view/3140124.htm
下面，贴代码：
开放寻址，POJ测试最快是219MS，125MS级别的代码不知是如何实现的==
#include <cstdio>
#include <cstring> int prime[]={,,,,,,,}; int x[],y[];
int savex[],savey[];
bool hash[]; inline int calHash(int x,int y)
{
return ((x<<)^y)&;
} void insert(int x,int y)
{
int h=calHash(x,y);
int add=prime[(x^y)&];
while(hash[h] && (savex[h]!=x || savey[h]!=y))
{
h+=add;
h&=;
}
hash[h]=true;
savex[h]=x;
savey[h]=y;
} bool find(int x,int y)
{
int h=calHash(x,y);
int add=prime[(x^y)&];
while(hash[h] && (savex[h]!=x || savey[h]!=y))
{
h+=add;
h&=;
}
if(hash[h] && savex[h]==x && savey[h]==y)
return true;
return false;
} bool calK(int a,int b)
{
if(x[a]==x[b])
return false;
if(y[a]==y[b])
return true;
if(((x[a]-x[b])&(<<))==((y[a]-y[b])&(<<)))
return true;
return false;
} inline int Abs(int n)
{
return n<?-n:n;
} int main()
{
// freopen("in.txt","r",stdin);
int n;
while(~scanf("%d",&n) && n)
{
memset(hash,,sizeof(hash));
for(int i=;i<n;i++)
{
scanf("%d%d",x+i,y+i);
insert(x[i],y[i]);
} int count=;
for(int i=;i<n;i++)
for(int k=i+;k<n;k++)
{
if(calK(i,k))
{
int _y=Abs(y[i]-y[k]);
int _x=Abs(x[i]-x[k]);
if(find(x[i]+_y,y[i]-_x) &&
find(x[k]+_y,y[k]-_x))
count++;
}
}
printf("%d\n",count);
}
}
链式，即发现冲突就在当前位置加一个槽。POJ上最快319MS。当然，每次新建的槽并没有delete，会造成内存泄露，现实中还是别这么干，或者及时delete吧。
#include <cstdio>
#include <cstring> struct Point
{
int x,y;
bool operator<(const Point& cmp) const
{
return x==cmp.x?y<cmp.y:x<cmp.x;
}
} point[],p,q; struct Hash
{
int x,y;
Hash* next;
Hash()
{
next=;
}
} hash[]; inline int calHash(int x,int y)
{
return ((x<<)^y)&;
} void insert(int x,int y)
{
int h=calHash(x,y);
Hash* p=&hash[h];
while(p->next)
p=p->next;
p->x=x;
p->y=y;
p->next=new Hash();
} bool find(int x,int y)
{
int h=calHash(x,y);
Hash* p=&hash[h];
while(p->next)
{
if(p->x==x && p->y==y)
return true;
p=p->next;
}
return false;
} bool calK(Point& a,Point& b)
{
if(a.x==b.x)
return false;
if(a.y==b.y)
return true;
if(((a.x-b.x)&(<<))==((a.y-b.y)&(<<)))
return true;
return false;
} inline int Abs(int n)
{
return n<?-n:n;
} int main()
{
// freopen("in.txt","r",stdin);
int n;
while(~scanf("%d",&n) && n)
{
memset(hash,,sizeof(hash));
for(int i=;i<n;i++)
{
scanf("%d%d",&point[i].x,&point[i].y);
insert(point[i].x,point[i].y);
} int count=;
for(int i=;i<n;i++)
for(int k=i+;k<n;k++)
{
if(calK(point[i],point[k]))
{
int _y=Abs(point[i].y-point[k].y);
int _x=Abs(point[i].x-point[k].x);
if(find(point[i].x+_y,point[i].y-_x) &&
find(point[k].x+_y,point[k].y-_x))
count++;
}
}
printf("%d\n",count);
}
}
最简单的办法，set……1360MS
#include <cstdio>
#include <cstring>
#include <set>
using namespace std; struct Point
{
int x,y;
bool operator<(const Point& cmp) const
{
return x==cmp.x?y<cmp.y:x<cmp.x;
}
} point[],p,q; set<Point> ss; bool calK(Point& a,Point& b)
{
if(a.x==b.x)
return false;
if(a.y==b.y)
return true;
if(((a.x-b.x)&(<<))==((a.y-b.y)&(<<)))
return true;
return false;
} inline int Abs(int n)
{
return n<?-n:n;
} int main()
{
// freopen("in.txt","r",stdin);
int n;
while(~scanf("%d",&n) && n)
{
ss.clear();
for(int i=;i<n;i++)
{
scanf("%d%d",&point[i].x,&point[i].y);
ss.insert(point[i]);
} int count=;
for(int i=;i<n;i++)
for(int k=i+;k<n;k++)
{
if(calK(point[i],point[k]))
{
int _y=Abs(point[i].y-point[k].y);
int _x=Abs(point[i].x-point[k].x);
p.x=point[i].x+_y;
p.y=point[i].y-_x;
if(ss.find(p)==ss.end())
continue; p.x=point[k].x+_y;
p.y=point[k].y-_x;
if(ss.find(p)!=ss.end())
count++;
}
}
printf("%d\n",count);
}
}
三个版本是慢慢优化出来的，哈希函数也有区别。