id=2002">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;

}