pku 2002Squares 二分查找

#include<iostream>
#include<algorithm>
using namespace std;
struct node{
    int x, y;
}p[1007];
int n;
int cmp(node a, node b)
{
    if(a.x==b.x)    return a.y < b.y;
    return a.x <b.x;
}
bool bsearch(int x, int y, int low, int high)
{
    while(low <= high)
    {
        int m=(low + high)/2;
        if(p[m].x == x && p[m].y == y)    return true;
        else if(p[m].x < x)    low=m+1;
        else if(p[m].x >x)    high=m-1;
        else{
            if (p[m].y > y)
            high = m -1;
            else
            low = m + 1;
        }
    }
    return false;
}
int main()
{
    int i, j, sum;
    while(cin>>n && n)

    {
        sum=0;
        for(i=0; i<n; ++i)
        {
            cin>>p[i].x>>p[i].y;
        }
        sort(p, p+n, cmp);
        for (i = 0; i < n; ++i)
        {
            for (j = i + 1; j < n; ++j)
            {
                int x3=p[j].x-(p[j].y-p[i].y);
                int y3=p[j].y+(p[j].x-p[i].x);
                if(!bsearch(x3,y3,0,n))
                    continue;
                int x4=p[i].x-(p[j].y-p[i].y);
                int y4=p[i].y+(p[j].x-p[i].x);
                if(!bsearch(x4,y4,0,n))
                    continue;
                sum++;
            }
        }
        printf("%d\n",sum/2);
    }
    return 0;
}