kmjp's blog

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

AtCoder ABC #157 : F - Yakiniku Optimization Problem

しょうもない見落としで手間取ってしまった。
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を考慮し忘れてしばらくバグってしまった…。