Codeforces 182 A. Battlefield

問題

xy平面上の点Aから点Bまで移動したい。

レーザーが、a秒間のチャージの後でb秒間照射される、その後またa秒間のチャージの後でb秒間照射される
という規則で照射される。
レーザーがチャージ中の時間は、1単位時間あたり1単位距離の移動が可能であるが、レーザーの照射されている時間は、塹壕に入っていなければならない。

塹壕はn個あり、それぞれ線分で表される。
塹壕に出入りする時間は０とみなすものとし、出入りは好きな場所から行えるものとする。
このとき、点Bまで移動するのにかかる時間の最小値を求めよ。

点Bまで移動できない場合は-1を出力せよ。

制約条件

塹壕の数≦1000
塹壕はx軸またはy軸に平行な線分として表される。
塹壕の長さはb以下である。

方針

時間を離散化して考える。
レーザーの周期の何回目の開始の直前までにその塹壕に行けるかは、
塹壕を頂点とし、線分同士の距離がa以下であるような塹壕同士に辺を張ったグラフで、
幅優先探索をすることで求まる。

点Bの直前の塹壕から、Bまでの距離だけは普通に足す。

ソースコード

ゼロ割の例外を出しまくったらTLEになった。
ゼロ割をなくすようにしても1900ms
なんでこんなに遅いんだろう。

bool v[1010];
L ss[1010];

void run()
{
	int n, a, b, ax, ay, bx, by;
	scanf("%d%d%d%d%d%d%d", &a, &b, &ax, &ay, &bx, &by, &n);
	
	rep(i, n){
		int sx, sy, tx, ty;
		scanf("%lf%lf%lf%lf", &ss[i].F.real(), &ss[i].F.imag(),
			&ss[i].S.real(), &ss[i].S.imag());
	}
	
	ss[n].F.real() = ss[n].S.real() = ax;
	ss[n].F.imag() = ss[n].S.imag() = ay; n++;
	ss[n].F.real() = ss[n].S.real() = bx;
	ss[n].F.imag() = ss[n].S.imag() = by; n++;
	
	vector<vi> e(n);
	
	rep(i, n) rep(j, i){
		double dist;
		if(i >= n-2 && j >= n-2) dist = abs(ss[i].F - ss[j].F);
		else if(i >= n-2) dist = distanceSP(ss[j], ss[i].F);
		else if(j >= n-2) dist = distanceSP(ss[i], ss[j].F);
		else dist = distanceSS(ss[i], ss[j]);
		
		if(dist < a + EPS){
			e[i].pb(j);
			e[j].pb(i);
		}
	}
	rep(i, n) v[i] = 0;
	
	queue<pi> q;
	q.push(mp(0, n-2));
	v[n-2] = 1;
	double ans = 1e9;
	
	while(!q.empty()){
		int c = q.front().second;
		int turn = q.front().first; q.pop();
		
		rep(i, e[c].size()) {
			if(!v[e[c][i]]) q.push(mp(turn + 1, e[c][i]));
			if(e[c][i] == n-1){
				ans = min(ans, 1.0 * (a + b) * turn + distanceSP(ss[c], ss[n-1].F));
			}
			v[e[c][i]] = 1;
		}
	}
	
	if(ans == 1e9) puts("-1");
	else printf("%.20f\n", ans);
}