POJ 2002 – Squares [几何+二分]

Link

点击打开poj题目链接

Problem

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.

Mean

给你N个整数点的坐标,让你找出最多能够形成多少个正方形。N最大为1000

Analyse

四重暴力肯定是不行了,就两层暴力枚举两个点AB然后算出另外两个点CD。刚开始以为CD可能不是整数然后上double几何模板果断超时了。然后推了下公式发现CD的坐标可以直接求出来,分两种情况,在逆时针和顺时针两个正方形。但是这需要枚举的AB是有序的,否则公式就不对了。排序后用二分找一下CD即可。这题充分暴露了几何分析不严谨的毛病….

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))
                    ++cnt;
            }
        }
        printf("%lld\n", cnt>>1);
    }
    return 0;
}

欢迎留言