kmjp's blog

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

Codeforces #340 Div2. C. Watering Flowers

CもDも落とすという雑さがひどい。Div2回で助かった…。
http://codeforces.com/contest/617/problem/C

問題

2次元座標上で、2つのスプリンクラーとN個の花がある。
スプリンクラーはそれぞれ自身を中心とした半径R1,R2の範囲の円内に水を撒くことができる。

スプリンクラーの散水範囲を調整し、各花が少なくとも片方の水を届くようにしたい。
(R1^2+R^2)を最小化せよ。

解法

R1の上限を各花に届くギリギリの範囲にしたケースで、残りの花をR2でカバーするのに必要な値を求めればよい。
コーナーケースとして、全て2つ目のスプリンクラーで賄うケースがあるので注意すること。
自分はこれで落としたし、逆にHackも何個か取れた。

int N,X1,Y1,X2,Y2;
ll X[2020],Y[2020];
ll R1[2020],R2[2020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X1>>Y1>>X2>>Y2;
	
	set<ll> cand;
	cand.insert(0);
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		R1[i]=(X[i]-X1)*(X[i]-X1)+(Y[i]-Y1)*(Y[i]-Y1);
		R2[i]=(X[i]-X2)*(X[i]-X2)+(Y[i]-Y2)*(Y[i]-Y2);
		cand.insert(R1[i]);
	}
	
	ll mi=1LL<<62;
	FORR(r,cand) {
		ll ma=0;
		FOR(i,N) if(R1[i]>r) ma=max(ma,R2[i]);
		mi=min(mi,r+ma);
	}
	cout<<mi<<endl;
}

問題

GCJ2009 R2Dを簡単にした感じ。
Dashboard - Round 2 2009 - Google Code Jam

広告を非表示にする