kmjp's blog

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

Codeforces #194 Div1 E. Summer Earnings

この回はEも比較的簡単だったのか、正答者が多い。
http://codeforces.com/contest/333/problem/E

問題

2次元座標上でN個の点の座標が与えられる。
これらの点から3個を選択し、互いに交差しない同一半径の円を作ることを考える。

条件を満たす最大の半径を求めよ。

解法

TL=9sという珍しい問題。
想定解はO(N^2*logN)のようだが、自分はちょっと枝刈りしたO(N^3)で無理やり通してしまった。

3点A,B,Cを選択した場合、互いに交差しない円の最大半径はmin(|AB|,|BC|,|CA|)/2である。
まず前処理として、各点Xに対し、他の頂点Yまでの距離|XY|を事前に求め、かつ距離順で頂点番号Yをソートしていく。

次に、A,Bを総当たりし、|AB|/2が求める半径となりうるかを求める。
A,Bが定まるとき、残りCをどう高速に求めるかが問題。
まずlower_boundを用いて|AX|≧|AB|となる頂点Xの候補と、|BY|≧|AB|となる頂点Yの候補を求める。

  • X及びYの候補数がそれぞれN/2以上なら、両方に属する頂点が1個以上ありそれをCとして選べる。
  • X及びYの候補数がそれぞれN/2未満なら、少ない方の候補Zに対して総当たりし、|AZ|≧|AB|かつ|BZ|≧|AB|であるか判定すればよい。
int N,X[4000],Y[4000];
int D[4000][4000];
pair<int,int> P[4000][4000];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>X[i]>>Y[i];
	FOR(i,N) {
		FOR(j,N) D[i][j]=(X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]);
		FOR(j,N) P[i][j]=make_pair(D[i][j],j);
		sort(P[i],P[i]+N);
	}
	
	int ma=0;
	FOR(x,N) for(y=x+1;y<N;y++) if(D[x][y]>ma) {
		i=lower_bound(P[x],P[x]+N,make_pair(D[x][y],-1))-P[x];
		j=lower_bound(P[y],P[y]+N,make_pair(D[x][y],-1))-P[y];
		if(i<N/2&&j<N/2) {
			ma=D[x][y];
		}
		else if(i>j) {
			for(;i<N;i++) {
				j=P[x][i].second;
				if(D[y][j]>=D[x][y]) {
					ma=D[x][y];
					break;
				}
			}
		}
		else {
			for(;j<N;j++) {
				i=P[y][j].second;
				if(D[x][i]>=D[x][y]) {
					ma=D[x][y];
					break;
				}
			}
		}
		
	}
	_P("%.12lf\n",sqrt(ma)/2);
}

まとめ

9秒とはいえ、O(N^3)は想定ではないんだろうなぁ…。