3432:Count Squares

PKU

keyword

幾何　C++

概要

2次元平面上の点が与えられたとき(2000個以下)、正方形がいくつできるか求める問題。
2点決めて正方形をなすような残りの2点があるかどうか2分探索すればよい。重複に注意。

int main(){
    int x, y, dx, dy;
    pi ps[2000];
    int i, j, n, ans = 0;
    scanf("%d",&n);

    REP(i,n){
        scanf("%d%d", &x, &y);
        ps[i] = MP(x,y);
    }

    sort(ps,ps+n);

    REP(i,n)REP(j,n)if(i!=j){
        dx = ps[i].fs - ps[j].fs;
        dy = ps[i].sc - ps[j].sc;
        if(binary_search(ps,ps+n,MP(ps[i].fs+dy, ps[i].sc-dx))
         && binary_search(ps,ps+n,MP(ps[j].fs+dy, ps[j].sc-dx)))
            ans++;
    }

    printf("%d\n",ans/4);

    return 0;
}