PKU 1859 The Perfect Symmetry
http://poj.org/problem?id=1859
n個の点が入力される。
全ての点が対称となれるような点が存在するなら、それを求めろというような問題
似たような問題を見た気がします。
setを使ってTLEしまくりました。
int getnum(){ char ch; while(isspace(ch=getchar())); if(ch=='-') return -getnum(); int ret=ch&15; while(isdigit(ch=getchar())) ret=(ret<<3)+(ret<<1) + (ch&15); return ret; } int n; PI in[20000]; struct val{ val* next; PI va; }; const int hashMod=1<<18; val* table[hashMod]; val ent[20000]; int esz; bool app(const PI key){ int hash=(key.F*108353+key.S)&hashMod - 1; for(val* p=table[hash];p;p=p->next) if(p->va==key) return true; return false; } void insert(const PI key){ int hash=(key.F*108353+key.S)&hashMod - 1; val* p=ent+esz++; p->next = table[hash]; p->va = key; table[hash] = p; } void solve(){ ll sx = 0, sy = 0; esz = 0; memset(table,0,sizeof(table)); rep(i,n){ in[i].F = getnum(); in[i].S = getnum(); //scanf("%d%d",&in[i].F,&in[i].S); in[i].F *= 2; in[i].S *= 2; sx += in[i].F; sy += in[i].S; insert(in[i]); } if(sx%n || sy%n){ puts("This is a dangerous situation!"); return; } sx /= n; sy /= n; sx *= 2; sy *= 2; rep(i,n){ if(app(mp(sx-in[i].F,sy-in[i].S))) continue; puts("This is a dangerous situation!"); return; } printf("V.I.P. should stay at (%.1f,%.1f).\n",sx/4.,sy/4.); } main(){ while(scanf("%d",&n),n) solve(); }