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); } }