poj2002——求点能组成正方形的个数（二分或hash）

题目链接：http://poj.org/problem?id=2002

A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles. It is also a polygon such that rotating about its centre by 90 degrees gives the same polygon. It is not the only polygon with the latter property, however, as a regular octagon also has this property. So we all know what a square looks like, but can we find all possible squares that can be formed from a set of stars in a night sky? To make the problem easier, we will assume that the night sky is a 2-dimensional plane, and each star is specified by its x and y coordinates.

Input

The input consists of a number of test cases. Each test case starts with the integer n (1 <= n <= 1000) indicating the number of points to follow. Each of the next n lines specify the x and y coordinates (two integers) of each point. You may assume that the points are distinct and the magnitudes of the coordinates are less than 20000. The input is terminated when n = 0.

Output

For each test case, print on a line the number of squares one can form from the given stars.

Sample Input

4

1 0

0 1

1 1

0 0

9

0 0

1 0

2 0

0 2

1 2

2 2

0 1

1 1

2 1

4

-2 5

3 7

0 0

5 2

0

Sample Output

1

6

1

题目翻译：

正方形是四面多边形，其边的长度相等，相邻边形成 90 度角。它还是一个多边形，围绕其中心旋转 90 度，给出相同的多边形。它不是具有后一个属性的唯一多边形，但是，因为常规八角形也有此属性。‎ ‎所以，我们都知道一个正方形是什么样子，但我们能找到所有可能的正方形，可以形成从一组星星在‎ ‎夜空？为了使问题更容易，我们将假设夜空是一个二维平面，每个恒星由其 x 和 y 坐标指定。‎

‎输入‎

‎输入由许多测试用例组成。每个测试用例都以整数 n （1 <= n <= 1000） 开头，指示要遵循的点数。接下来的 n 行中的每一条都指定每个点的 x 和 y 坐标（两个整数）。您可以假定点是不同的，坐标的幅度小于 20000。当 n = 0 时，输入终止。‎

‎输出‎

‎对于每个测试用例，在一行上打印一个正方形数，从给定的星形形成。

题意理解：

给你n个点，求这n个点能组成正方形的个数。

这个题有两种做法，一种是二分，一种是hash，

首先需要知道一个结论，即由两个点的坐标，可以得出正方形另外的两个点的坐标。

已知： (x1,y1) (x2,y2)

则： x3=x1+(y1-y2) y3= y1-(x1-x2)

x4=x2+(y1-y2) y4= y2-(x1-x2)

或

x3=x1-(y1-y2) y3= y1+(x1-x2)

x4=x2-(y1-y2) y4= y2+(x1-x2)

然后就可以直接暴力枚举两个点，在二分去找另外两个点。

#include

#include

#include

#include

using namespace std ;

const double eps=1e-6;

struct Point{

double x,y;

Point(double x=0,double y=0):x(x),y(y){}

}p[1005];

bool cmp(Point a,Point b){

if(a.x==b.x) return a.y

return a.x

}

bool judge(double x,double y,int n)

{

int l=0,r=n-1;

while(l<=r)

{

int m=(l+r)>>1;

if(fabs(p[m].x-x)

return true;

else if(p[m].x-x>eps||(fabs(p[m].x-x)eps) )

r=m-1;

else

l=m+1;

}

return false;

}

int main()

{

int n;

while(scanf("%d",&n)==1)

{

if(!n) break;

for(int i=0;i

scanf("%lf%lf",&p[i].x,&p[i].y);

sort(p,p+n,cmp);

int ans=0;

for(int i=0;i

for(int j=i+1;j

// if(i==j) continue ;

double x=(p[i].x+p[j].x)/2 ;

double y=(p[i].y+p[j].y)/2 ;

double xx=p[i].x-x;

double yy=p[i].y-y;

if(judge(x+yy,y-xx,n)&&judge(x-yy,y+xx,n))

ans++;

}

}

printf("%d\n", ans/2) ;

}

return 0;

}

另一种做法是二维点的哈希，抛一下网上大牛的链接：https://blog.csdn.net/lyy289065406/article/details/6647405