POJ2002POJ3432 Squares(二分||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)

我们只用其中一个，这样最后只会算每条边对应的左上方或者右下方的矩形，这样只有两条边对应的计算了一次，因此需要将计数/2。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct node
{int x, y;
}a[2500];
int n;bool cmp(const node a,const node b)
{if (a.x == b.x)return a.y < b.y;elsereturn a.x < b.x;
}
bool find(int x, int y)//二分求点是否存在
{int left = 0, right = n;node u;u.x = x; u.y = y;while (left <= right){int mid = left + (right - left) / 2;if (a[mid].x == x&&a[mid].y == y)return true;else if (cmp(u, a[mid]))right = mid - 1;elseleft = mid + 1;}return false;
}int main()
{int x3, x4, y3, y4;while (scanf("%d", &n) && n){int count = 0;for (int i = 0; i < n; i++)scanf("%d%d", &a[i].x, &a[i].y);sort(a, a + n, cmp);			//要使用二分要先排序for (int i = 0; i < n; i++)for (int j = i + 1; j < n; j++){x3 = a[i].x + a[j].y - a[i].y;//这里可以由全等三角形得出y3 = a[i].y + a[i].x - a[j].x;x4 = a[j].x + a[j].y - a[i].y;y4 = a[j].y + a[i].x - a[j].x;if (find(x3, y3) && find(x4, y4))count++;}printf("%d\n", count/2);//只计算左上方和右上方的矩形，最后除以2}return 0;
}