Squares
非常好的一道二分，其实本来我是没有思路的，看了基神的题解之后才似乎明白了点。
题意：给出最多有1000个点，问这些点可以组成多少个正方形
分析：先想想怎么判断正方形吧，假如我现在有四个点A,B,C,D，，因为边不一定是平行于x轴的，可能是倾斜的，如何判断四个点组成的四边形是正方形呢？以A点为中心，AB为轴，绕A点顺时针或者逆时针转动90度，就可以得到一个点D’ , 同样的方法，以B
点为中心，BA为轴，绕B点顺时针或者逆时针转动90度，就可以得到一个点C’ ,如果D’ 的坐标与D的坐标相同，如果C’的坐标与C的坐标相同, 那么就可以确定这个四边形是正方形了。
旋转可以用这个公式：
任意点(x,y)，绕一个坐标点(rx0,ry0)逆时针旋转a角度后的新的坐标设为(x0, y0)，有公式：x0= (x – rx0)*cos(a) – (y – ry0)*sin(a) + rx0 ;y0= (x – rx0)*sin(a) + (y – ry0)*cos(a) + ry0 ;
既然知道如何判断正方形了，那么接下来，我只需要在给定的点里面每次取出两个点，A，B，【这里O（N^2）的复杂度】，求出对应的C’,D’【由于旋转方向不同，会有两个这样的解】，然后判断在这些给定的点里面有没有点与C’,D’重合即可，如果我再暴力的去遍历，最终复杂度会变成O（N^3），TLE无疑，这个时候，二分来作用了，我刚开始就把点给排序，然后只需要对点进行二分查找就OK了，那么这个时候我的复杂度是O（N^2*log(N)）。当然，要注意不要重复判断了，也就是我取A，B的时候，还有二分的时候注意一下范围就可以了。
#include <cmath>#include <queue>#include <cstdio>#include <string>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int maxn = 1000+5;int N,ans;struct SPoint {double x,y;SPoint() {}SPoint(int xx,int yy) : x(xx), y(yy) {}bool operator < (const SPoint& p) const {if(x == p.x) return y < p.y;return x < p.x;}bool operator == (const SPoint& p) const {return x==p.x&&y==p.y;}}pnt[maxn];//任意点(x,y)，绕一个坐标点(rx0,ry0)逆时针旋转a角度后的新的坐标设为(x0, y0)，有公式：//x0= (x – rx0)*cos(a) – (y – ry0)*sin(a) + rx0 ;//y0= (x – rx0)*sin(a) + (y – ry0)*cos(a) + ry0 ;void transXY(SPoint A, SPoint B, SPoint &C, int f) {int tx = B.x – A.x, ty = B.y – A.y;C.x = A.x – ty * f;C.y = A.y + tx * f;}int main() {//freopen("input.in","r",stdin);while(~scanf("%d",&N)&&N){ans = 0;for(int i = 0;i < N;i++) scanf("%lf %lf",&pnt[i].x,&pnt[i].y);sort(pnt,pnt+N);for(int i = 0;i < N-3;i++)//①{for(int j = i+1;j < N-2;j++)//②{SPoint C,D;transXY(pnt[i],pnt[j],C,1);transXY(pnt[j],pnt[i],D,-1);if(binary_search(pnt+j,pnt+N,C)&&binary_search(pnt+j,pnt+N,D)) ans++; //③transXY(pnt[i],pnt[j],C,-1);transXY(pnt[j],pnt[i],D,1);if(binary_search(pnt+j,pnt+N,C)&&binary_search(pnt+j,pnt+N,D)) ans++; //④ 注意这四个地方，避免重复判断}}printf("%d\n",ans);}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
竞争颇似打网球，与球艺胜过你的对手比赛，
