PKU 2526 Center of symmetry
http://poj.org/problem?id=2526
点がn個与えられる。
この時ある点が存在して、すべての点に対してその点を中心に対象移動させると、もとのn個の点が得られるかどうかを判定しろというような問題。
scanf+setでTLEしましたが、binary_searchで乗り切りました。
PI in[10000]; string solve(){ int n; scanf("%d",&n); ll sx=0,sy=0; rep(i,n){ scanf("%d%d",&in[i].F,&in[i].S); sx+=in[i].F,sy+=in[i].S; } sort(in,in+n); if(2*sx%n || 2*sy%n)return "no"; rep(i,n){ ll px=2*sx/n-in[i].F; ll py=2*sy/n-in[i].S; if(max<ll>(llabs(px),llabs(py))>10000000)return "no"; if(!binary_search(in,in+n,mp((int)px,(int)py)))return "no"; } return "yes"; } main(){ int c; scanf("%d",&c); while(c--) cout<<solve()<<endl; }