しょうもない見落としで手間取ってしまった。
https://atcoder.jp/contests/abc157/tasks/abc157_f
問題
2次元座標中にN個の点(X[i],Y[i])がある。
各点の速度が最大C[i]で移動するとき、K個以上の点が同一箇所に集まるのにかかる最短時間を求めよ。
解法
二分探索で解くことを考える。
時間Tを決めると、各点の移動範囲は半径T/C[i]の円となる。
このうちK個以上が共通部分を持つケースを求めよう。
Tを徐々に大きくしていくと、円同士が交差していくことになり、その際共通部分が生じる。
そこで、2円の交点を中心の候補として総当たりしよう。
K=1のケースに問題にならないよう、各円の中心も候補にしておくとよい。
int N,K; double X[100],Y[100],C[100]; double mi=1e9; int go(double x,double y,double T) { int count=0; int i; FOR(i,N) if(hypot(x-X[i],y-Y[i])*C[i]<=T+(1e-9)) count++; return count; } double ok(double T) { int i,j; FOR(i,N) if(go(X[i],Y[i],T)>=K) return 1; FOR(j,N) FOR(i,j) { double r1=T/C[i]; double r2=T/C[j]; double d=hypot(X[i]-X[j],Y[i]-Y[j]); if(r1+r2<d) continue; if(r1+d<r2) continue; if(d+r2<r1) continue; double s=(r1+r2+d)/2; double a=sqrt(s*(s-r1)*(s-r2)*(s-d)); double h=a/d*2; double d2=sqrt(r1*r1-h*h); double dx1=(X[j]-X[i])/d; double dy1=(Y[j]-Y[i])/d; double dx2=dy1; double dy2=-dx1; for(int cx=-1;cx<=1;cx+=2) { for(int cy=-1;cy<=1;cy+=2) { double tx=X[i]+cx*d2*dx1+cy*h*dx2; double ty=Y[i]+cx*d2*dy1+cy*h*dy2; if(go(tx,ty,T)>=K) return 1; } } } return 0; } void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; FOR(i,N) cin>>X[i]>>Y[i]>>C[i]; double L=0,R=1e9; FOR(i,100) { double M=(L+R)/2; if(ok(M)) R=M; else L=M; } _P("%.12lf\n",L); }
まとめ
epsを考慮し忘れてしばらくバグってしまった…。