POJ 2002 Squares 几何， 二分

题目意思：给n个点，求可以组成几个正方形

本题要点：
1、 正方形已知两点(x1, y1), (x2, y2) 求另外两点的坐标
x3 = x1 + (y1 - y2), y3 = y1 - (x1 - x2)
x4 = x2 + (y1 - y2), y4 = y2 -(x1 - x2)
2、 二分查找

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN =1010;
int n;struct Point
{
    int x, y;
}points[MaxN];bool cmp(const Point& a, const Point& b)
{
    if(a.x != b.x){
    return a.x < b.x;}return a.y < b.y;
}bool search(int x, int y)
{
    int left = 0, right = n, mid = 0;// 存在性查找while(left <= right){
    mid = (left + right) / 2;if(x == points[mid].x && y == points[mid].y){
    return true;}else if(points[mid].x > x || (points[mid].x == x && points[mid].y > y)){
    right = mid - 1;}else{
    left = mid + 1;}}return false;
}void solve()
{
    sort(points, points + n, cmp);int ans = 0;int x1, y1, x2, y2;for(int i = 0; i < n; ++i){
    for(int j = i + 1; j < n; ++j){
    x1 = points[i].x + (points[i].y - points[j].y);//根据公式求点3y1 = points[i].y - (points[i].x - points[j].x);if(!search(x1, y1)){
    continue;}x2 = points[j].x + (points[i].y - points[j].y);//根据公式求点4y2 = points[j].y - (points[i].x - points[j].x);if(!search(x2, y2)){
    continue;}++ans;}}printf("%d\n", ans / 2);
}int main()
{
    while(scanf("%d", &n) && n){
    for(int i = 0; i < n; ++i){
    scanf("%d%d", &points[i].x, &points[i].y);}solve();}return 0;
}/* 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 *//* 1 6 1 */