AOJ 1171 Laser Beam Reflections（レーザー光の反射）

問題

座標平面上に、線分で表される鏡がn枚置いてある。
鏡は両面でレーザー光を反射することができる。

スタートからゴールまで、レーザー光をたどり着かせるための、
光の最短移動距離を求めよ。

制約条件

n≦5
座標は全て100以下の整数。
最適解において反射は5回以下であることが保証されている。
最適解において鏡の両端から0.001以下の点で光が反射することはない。

方針

使う鏡とその順番を全通り試す。

鏡で光が反射されることを、
鏡を対称軸に、全ての点が線対称に移動すると考える。
すると、光線はただのまっすぐな線分として考えることが出来る。

線分が、使う鏡の順番どおりに鏡と交わらなかったり、
途中で他の鏡にぶつかってしまったりしたらその解は捨てる。

ソースコード

int n;
vector<L> ms;
P start, goal;

double solve(vi &use){
	vector<L> tms = ms;
	P target = goal;
	rep(i, use.size()){
		L line = tms[use[i]];
		rep(j, n) rep(k, 2) tms[j][k] = reflection(line, tms[j][k]);
		target = reflection(line, target);
	}
	P cur = start;
	tms = ms;
	
	rep(i, use.size()){
		L beam(cur, target);
		if(!intersectSS(beam, tms[use[i]])) return INF; //使う鏡と交わらない
		
		P next = crosspoint(beam, tms[use[i]]);
		beam = L(cur, next);
		rep(j, n) if(j != use[i]){
			int tmp = ccw(cur, tms[j][0], tms[j][1]);
			if(tmp == 0 || tmp == 2 || !intersectSS(beam, tms[j])) continue;
			
			return INF; //使わない鏡と交わる
		}
		
		L line = tms[use[i]];
		rep(j, n) rep(k, 2) tms[j][k] = reflection(line, tms[j][k]);
		cur = next;
	}
	rep(i, n){
		int tmp = ccw(cur, tms[i][0], tms[i][1]);
		if(tmp == 0 || tmp == 2) continue;
		if(intersectSS(L(cur, target), tms[i])) return INF;
	}
	
	return abs(start - target);
}

double ans;
void rec(vi &use){
	ans = min(ans, solve(use));
	if(use.size() < 5){
		rep(i, n) if(use.empty() || use.back() != i){
			use.pb(i);
			rec(use);
			use.pop_back();
		}
	}
}

int main()
{
	while(cin >> n, n){
		ms.clear();
		
		rep(i, n){
			int x, y, X, Y;
			cin >> x >> y >> X >> Y;
			ms.pb(L(P(x, y), P(X, Y)));
		}
		cin >> goal.real() >> goal.imag();
		cin >> start.real() >> start.imag();
		
		ans = INF;
		vi use;
		rec(use);
		printf("%.20f\n", ans);
	}
	return 0;
}