kmjp's blog

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

AtCoder ARC #064 : E - Cosmic Rays

こっちの方がすんなり。
http://arc064.contest.atcoder.jp/tasks/arc064_c

問題

2次元座標上で点Sから点Tに速度1移動したい。
その際、移動した時間分放射線を浴びてしまうが、いくつか円形のバリアがあり、その内部を移動する間は放射線を浴びない。
これらの円形バリアは固定で、その位置(X(v),Y(v))と半径R(v)が与えられる。
最適に移動した場合、放射線を浴びる最短時間を求めよ。

解法

S,Tも半径0のバリアとみなすとやりやすい。

2つのバリアa,bの中心距離をD(a,b)とすると、max(0,D(a,b)-R(a)-R(b))がその間を移動する際にで放射線を浴びる時間となる。
あとは円の中心間の移動について、ダイクストラの要領で最短経路を求める。

ll XS,YS,XT,YT;
int N;
double X[5050],Y[5050],R[5050];
double D[5050];



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X[0]>>Y[0]>>X[1]>>Y[1];
	R[0]=R[1]=0;
	cin>>N;
	FOR(i,N) {
		cin>>X[i+2]>>Y[i+2]>>R[i+2];
	}
	N+=2;
	for(i=1;i<N;i++) D[i]=1e15;
	
	priority_queue<pair<double,int>> P;
	P.push({0,0});
	
	while(P.size()) {
		double cost=-P.top().first;
		int cur=P.top().second;
		P.pop();
		if(cost!=D[cur]) continue;
		
		FOR(i,N) if(i!=cur) {
			double d=hypot(X[i]-X[cur],Y[i]-Y[cur])-R[i]-R[cur];
			if(d<0) d=0;
			if(D[i]>D[cur]+d) {
				D[i]=D[cur]+d;
				P.push({-D[i],i});
			}
		}
	}
	
	
	_P("%.12lf\n",D[1]);
}

まとめ

今回これが一番コード量が多い。