POJ 2002

正方形の2つの頂点を決めてしまってから、残りの2頂点が存在するかを二分探索する

#include <cstdio>
#include <algorithm>
using namespace std;

#define X first
#define Y second
typedef pair<int, int> P;
int N;
P stars[1000];
int main(){
	while(scanf("%d", &N) && N != 0){
		int ans = 0;
		for(int i = 0; i < N; i++){
			scanf("%d %d", &stars[i].X, &stars[i].Y);
		}
		sort(stars, stars + N);
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(i == j) continue;
				P a = stars[i], b = stars[j];
				int dx = b.X - a.X;
				int dy = b.Y - a.Y;
				P c, d;
				c.X = a.X + dy; c.Y = a.Y - dx;
				d.X = b.X + dy; d.Y = b.Y - dx;
				if(binary_search(stars, stars + N, c)
				 && binary_search(stars, stars + N, d) ){
					ans++;
				}
			}
		}
		printf("%d\n", ans/4);
	}
}