2526:Center of symmetry

keyword

幾何　対象　C++

概要

2次元平面上のユニークな点がn(<10^5)個与えられる。座標は整数。このとき、対象点sが存在するかどうかを判定する問題。ただし、sが対象点であるとは任意のiに対してp_i - s = s - p_jとなるようなjが存在するときにいう。
幾何はICPCで自分の担当なので復習の意味も込めて丁寧に書く。
対象点が分かれば判定するのは楽なので、対象点を探す方法を考える。重心であることに気が付けば問題は解けたも同然(点がユニークであることに注意)。
しかし対象点が存在するかどうかを探すので誤差に気を配る必要がある。対象点が格子点上にあるとは限らないからである。実は対象点の座標は整数or整数+0.5なのでdoubleで十分誤差なく表現できるけど、座標を2倍にすることで完全に整数に落とせる。
後は実装するだけ。座標をpairで持つと、PKUだとTLEが怖いのでlong long一つにまとめた。

int main(){
    int rept, n, i, d=500000000ll;
    ll x, y, cx, cy;
    ll ps[10002];
    scanf("%d",&rept);

    LOOP(rept){
        scanf("%d",&n);
        cx = cy = 0;
        REP(i,n){
            scanf("%lld%lld",&x,&y);
            cx += x;
            cy += y;
            ps[i] = 2*x*d + 2*y;
        }
        if(cx%n && cy%n){
            printf("no\n");
            continue;
        }
        cx /= n;
        cy /= n;

        REP(i,n){
            ps[i] -= 2*cx*d + 2*cy;
        }

        sort(ps,ps+n);
        REP(i,n)if(!binary_search(ps,ps+n,-ps[i]))break;
        if(i==n)printf("yes\n");
        else printf("no\n");
    }

    return 0;
}