【题意】给出n个二维平面上的坐标，求出这n个坐标最多能够构成多少个正方形。
【解题思路】自己完全不会做，只好看网上题解了，现在把Hash和二分的解法展示如下，首先说一说解题的思路，
通过n最大为1000可以推测，应该是n^2左右的效率，所以我们先枚举两个点，然后通过这两个点再求出另外两个点的坐标，在输入的集合中查找是否存在这两个点，如果存在的话就可以构成一个正方形。
但是枚举也有一定的方法，我们不能随便枚举，因为有很多种形状的正方形，我们也不知道这两个点是正方形的哪两个点。首先，我们要先将所有的点按照x,y的大小排好序，然后遍历的时候取a[i]和a[j]两个点，且i<j,即a[i].x<a[j].x || a[i].x==a[j].x&&a[i].y<a[j].y。这样子我们就可以自定义是哪两个点：
比如这么一个正方形，我们已知1,2两个点的坐标为(a1,a2),(b1,b2)，那么我们怎么求得3,4两个点的坐标那？其实正方形有它的特殊性。
我们可以看出，上下做的两个三角形是全等的，所以说对于点3，点3的坐标为(a1+(b2-a2),a2-(b1-a1)),同理，点4的坐标为(b1+(b2-a2),b2-(b1-a1))。知道了这两个点，就可以去找了。
但是如果会问，那么如果遍历到的是1,3怎么办？其实不用管，因为这个是按从小到大来遍历的，那么1,2两个点肯定会被遍历到，就不用管1,3了。还有一点，如果我们遍历到的是2,4两个顶点，那么计算1,3两个定点的时候，计算公式是和知道1,3一样的。所以，对于每个四边形，我们都遍历了两遍，最后除以2即可。
对于查找的算法，我们可以用哈希或者二分即可。
【AC代码，Hash版本】
<span style="color: rgb(54, 46, 43); font-family: Arial; font-size: 14px; line-height: 26px; "><strong>Memory:</strong></span><span style="color: rgb(54, 46, 43); font-family: Arial; font-size: 14px; line-height: 26px;"> 4088K</span><span style="color: rgb(54, 46, 43); font-family: Arial; font-size: 14px; line-height: 26px; "><strong>Time:</strong></span><span style="color: rgb(54, 46, 43); font-family: Arial; font-size: 14px; line-height: 26px;"> 438MS</span><span style="color: rgb(54, 46, 43); font-family: Arial; font-size: 14px; line-height: 26px; "><strong>Language:</strong></span><span style="color: rgb(54, 46, 43); font-family: Arial; font-size: 14px; line-height: 26px;"> C++</span><span style="color: rgb(54, 46, 43); font-family: Arial; font-size: 14px; line-height: 26px; "><strong>Result:</strong></span><span style="color: rgb(54, 46, 43); font-family: Arial; font-size: 14px; line-height: 26px;"> </span><span style="font-family: Arial; font-size: 14px; line-height: 26px; color: blue;">Accepted</span>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdlib.h>
using namespace std;
const int nn = 1010;
struct node{
int x,y;
friend bool operator<(const node &aa,const node &bb)
{
if(aa.x==bb.x)
return aa.y<bb.y;
return aa.x<bb.x;
}
}a[nn];
int n;
int Hash[1000010],Next[1010];
bool check(int x,int y)
{
int key = abs(x+y);
int id = Hash[key];
while(id!=-1)
{
if(a[id].x==x&&a[id].y==y)
{
return true;
}
id = Next[id];
}
return false;
}
int main()
{
while(~scanf("%d",&n)&&n)
{
memset(Hash,-1,sizeof(Hash));
memset(Next,-1,sizeof(Next));
for(int i=0; i<n; i++) scanf("%d%d",&a[i].x,&a[i].y);
sort(a,a+n);
for(int i=0; i<n; i++)//hash.
{
int tmp = abs(a[i].x+a[i].y);
Next[i] = Hash[tmp]; //通过Next这个链式指针，为了check.
Hash[tmp] = i;
}
int ans = 0;
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
int px = a[j].x-a[i].x;
int py = a[j].y-a[i].y;
int xx = a[i].x+py;
int yy = a[i].y-px;
if(!check(xx,yy))continue; //3 point.
xx = a[j].x+py;
yy = a[j].y-px;
if(!check(xx,yy))continue;
ans++;
}
}
printf("%d\n",ans/2);//over count.
}
return 0;
}Memory: 172K Time: 1313MS Language: C++ Result: Accepted
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int nn = 1010;
struct node{
int x,y;
friend bool operator<(const node &aa,const node &bb)
{
if(aa.x==bb.x)
return aa.y<bb.y;
return aa.x<bb.x;
}
}a[nn];
int n;
bool Cmp(int x,int y,node &S)
{
if(x<S.x)return true;
if(x==S.x&&y<S.y)return true;
return false;
}
bool check(int x,int y)
{
int l=0,r=n;
int m;
while(l<=r)
{
m = (l+r)>>1;
if(a[m].x==x&&a[m].y==y)
return true;
if(Cmp(x,y,a[m]))
r = m-1;
else
l = m+1;
}
return false;
}
int main()
{
while(~scanf("%d",&n)&&n)
{
for(int i=0; i<n; i++) scanf("%d%d",&a[i].x,&a[i].y);
sort(a,a+n);
int ans = 0;
for(int i=0; i<n; i++)
{
for(int j=i+1; j<n; j++)
{
int px = a[j].x-a[i].x;
int py = a[j].y-a[i].y;
int xx = a[i].x+py;
int yy = a[i].y-px;
if(!check(xx,yy))continue;
xx = a[j].x+py;
yy = a[j].y-px;
if(!check(xx,yy))continue;
ans++;
}
}
printf("%d\n",ans/2);
}
return 0;
}
京公网安备 11010502036488号