kmjp's blog

競技プログラミング参加記です

Codeforces ECR #001 : C. Nearest vectors

新たに始まった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ならではの問題かも。