POJ 2002 – Squares [几何+二分]




A square is a 4-sided polygon whose sides have equal length and adjacent sides form 90-degree angles. It is also a polygon such that rotating about its centre by 90 degrees gives the same polygon. It is not the only polygon with the latter property, however, as a regular octagon also has this property.
So we all know what a square looks like, but can we find all possible squares that can be formed from a set of stars in a night sky? To make the problem easier, we will assume that the night sky is a 2-dimensional plane, and each star is specified by its x and y coordinates.





C++ Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;

const int maxn = 1024;
P p[maxn];

int main() {
    int n;
    while(~scanf("%d", &n) && n) {
        for(int i = 0; i < n; ++i) {
            scanf("%d%d", &p[i].first, &p[i].second);
        sort(p, p + n);
        long long cnt = 0;
        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                int dx = p[j].first - p[i].first;
                int dy = p[j].second - p[i].second;
                P c(p[i].first + dy, p[i].second - dx);
                P d(p[j].first + dy, p[j].second - dx);
                if(binary_search(p, p + n, c) && binary_search(p, p + n, d))
        printf("%lld\n", cnt>>1);
    return 0;