新たに始まったEducational Round。Pretestが余り強くないのか、ガンガンHackされます。
http://codeforces.com/contest/598/problem/C
問題
2次元座標において、原点以外の点がN個与えられる。
このうち2点と原点が成す角の最小値を求めよ。
解法
偏角でソートして、隣同士の点との角度の最小値を求めればよい。
…だけなのだが、誤差が厳しいのでlong doubleを使わないとWAする。
int N; int X[101010],Y[101010]; pair<long double,int> P[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>X[i]>>Y[i]; P[i]=make_pair(atan2l(Y[i],X[i]),i); } sort(P,P+N); P[N]=P[0]; P[N].first+=2*atan(1)*4; long double mi=1010; FOR(i,N) if(P[i+1].first-P[i].first<mi) { mi=P[i+1].first-P[i].first; x=P[i+1].second; y=P[i].second; } _P("%d %d\n",x+1,y+1); }
まとめ
Round2でも誤差ゲー出てるし、UnratedなEducational Roundならではの問題かも。