この回は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)は想定ではないんだろうなぁ…。