题目意思：给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);//根据公式求点3
y1 = points[i].y - (points[i].x - points[j].x);
if(!search(x1, y1))
{
continue;
}
x2 = points[j].x + (points[i].y - points[j].y);//根据公式求点4
y2 = 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
*/