http://acm.pku.edu.cn/JudgeOnline/problem?id=2002
http://acm.pku.edu.cn/JudgeOnline/problem?id=3432
枚举正方形一条对角线线上的2个点，很容易求出另外2个点，然后要检查另外2个点是否坐标都是整数，如果都是，然后看这2个点是否在点集中，要快速的判断一个点是否在点集中，可以先把点排序，然后二分查找，或者对点的坐标进行hash处理（速度更快）。
注意点：
在检查一个浮点数(x)是否是整数时，不能这样：
int x1=(int)x;
if(fabs(x-x1)<eps) //则是整数
因为对浮点数强制类型转换的结果是丢掉小数位
比如int(1.99999999999999999)=1
而1.999999999999999可以看做就是整数2,因此在对强制类型转换得到整数a后，要分别对a和a+1与原浮点数进行做差判断！
Hash版本：
#include <cstdio>
#include <cmath>const int maxn=2002;
const double eps=1.0e-6;
const int PRIME=9991;struct Point {
int x,y;
};struct HASH {
int cnt;
int next;
} hash[50000];
int hash1;
Point points[maxn];
inline
void Rotate(double x,double y,Point P,double &x1,double &y1) {
double vx=P.x-x,vy=P.y-y;
x1=x;y1=y;
x1-=vy;
y1+=vx;
}bool getsquare(Point p1,Point p2,Point &p3,Point &p4) {
double midx=(p1.x+p2.x)/2.0;
double midy=(p1.y+p2.y)/2.0;
double p3x,p3y,p4x,p4y;
Rotate(midx,midy,p1,p3x,p3y);
Rotate(midx,midy,p2,p4x,p4y);
p3.x=int(p3x);
p3.y=int(p3y);
p4.x=int(p4x);
p4.y=int(p4y);
bool tag=false;
if(fabs(p3.x+1-p3x)<eps) {p3.x++;tag=true;}
if(fabs(p3x-p3.x)<eps) tag=true;
if(!tag) return false;
tag=false;
if(fabs(p3.y+1-p3y)<eps) {p3.y++;tag=true;}
if(fabs(p3y-p3.y)<eps) tag=true;
if(!tag) return false;
tag=false;
if(fabs(p4.x+1-p4x)<eps) {p4.x++;tag=true;}
if(fabs(p4x-p4.x)<eps) tag=true;
if(!tag) return false;
tag=false;
if(fabs(p4.y+1-p4y)<eps) {p4.y++;tag=true;}
if(fabs(p4y-p4.y)<eps) tag=true;
if(!tag) return false;
return true;
}int Hash(int n) {
int i=n%PRIME;
while(hash[i].next!=-1) {
if(hash[hash[i].next].cnt==n) return 1;
else if(hash[hash[i].next].cnt>n) break;
i=hash[i].next;
}
hash[hash1].cnt=n;
hash[hash1].next=hash[i].next;
hash[i].next=hash1;
hash1++;
return 0;
}int Hash2(int n) {
int i=n%PRIME;
while(hash[i].next!=-1) {
if(hash[hash[i].next].cnt==n) return 1;
else if(hash[hash[i].next].cnt>n) return 0;
i=hash[i].next;
}
return 0;
}
int main() {
int n,x,y;
Point p1,p2;
scanf("%d",&n);
for(int i=0;i<PRIME;i++) hash[i].next=-1;
hash1=PRIME;
for(int i=0;i<n;i++) {
scanf("%d %d",&points[i].x,&points[i].y);
Hash((points[i].x+100000)*100000+points[i].y+100000);
}
int cnt=0;
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
bool ok=getsquare(points[i],points[j],p1,p2);
if(!ok) continue;
if(Hash2((p1.x+100000)*100000+p1.y+100000)==0) continue;
if(Hash2((p2.x+100000)*100000+p2.y+100000)==0) continue;
cnt++;
}
}
printf("%d\n",cnt/2);
return 0;
}
排序+二分查找版本：
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;const int maxn=2002;
const double eps=1.0e-6;struct Point {
int x,y;
};bool operator<(const Point& t1,const Point& t2) {
if(t1.x!=t2.x) return t1.x<t2.x;
if(t1.y!=t2.y) return t1.y<t2.y;
return false;
}
Point points[maxn];
inline
void Rotate(double x,double y,Point P,double &x1,double &y1) {
double vx=P.x-x,vy=P.y-y;
x1=x;y1=y;
x1-=vy;
y1+=vx;
}bool getsquare(Point p1,Point p2,Point &p3,Point &p4) {
double midx=(p1.x+p2.x)/2.0;
double midy=(p1.y+p2.y)/2.0;
double p3x,p3y,p4x,p4y;
Rotate(midx,midy,p1,p3x,p3y);
Rotate(midx,midy,p2,p4x,p4y);
p3.x=int(p3x);
p3.y=int(p3y);
p4.x=int(p4x);
p4.y=int(p4y);
bool tag=false;
if(fabs(p3.x+1-p3x)<eps) {p3.x++;tag=true;}
if(fabs(p3x-p3.x)<eps) tag=true;
if(!tag) return false;
tag=false;
if(fabs(p3.y+1-p3y)<eps) {p3.y++;tag=true;}
if(fabs(p3y-p3.y)<eps) tag=true;
if(!tag) return false;
tag=false;
if(fabs(p4.x+1-p4x)<eps) {p4.x++;tag=true;}
if(fabs(p4x-p4.x)<eps) tag=true;
if(!tag) return false;
tag=false;
if(fabs(p4.y+1-p4y)<eps) {p4.y++;tag=true;}
if(fabs(p4y-p4.y)<eps) tag=true;
if(!tag) return false;
return true;
}
int main() {
int n,x,y;
Point p1,p2;
while(scanf("%d",&n)!=EOF&&n) {
for(int i=0;i<n;i++) {
scanf("%d %d",&points[i].x,&points[i].y);
}
sort(points,points+n);
int cnt=0;
for(int i=0;i<n;i++) {
for(int j=i+1;j<n;j++) {
bool ok=getsquare(points[i],points[j],p1,p2);
if(ok)
if(binary_search(points,points+n,p1) && binary_search(points,points+n,p2))
cnt++;
}
}
printf("%d\n",cnt/2);
}
return 0;
}
