skyaozoraの日記

AOJ1171 レーザー光の反射

15:28

2010年の国内予選のG問題。光が逆行するのを許してしまっていて答えが合わず苦しんだ。

//10ICPC国内予選G レーザー光の反射 (AOJ1171)
//include、ライブラリ略
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
seg se[8][8];
int zyo[8][8];
double cal(vector<int> a,int n,Pt ta,Pt le){
	int m=a.size();
	rep(i,m-1){
		if(a[i]==a[i+1]) return inf;
	}
	rep(i,m) rep(j,n){
		if(j!=a[i]) se[i+1][j]=seg(ref(se[i][a[i]].s,se[i][a[i]].t,se[i][j].s),ref(se[i][a[i]].s,se[i][a[i]].t,se[i][j].t));
		else se[i+1][j]=se[i][j];
	}
	rep(i,m) ta=ref(se[i][a[i]].s,se[i][a[i]].t,ta);
	vector<Pt> p;p.pb(le);
	rep(i,m){
		if(!iSSstrict(ta,p[i],se[i][a[i]].s,se[i][a[i]].t)) return inf;
		p.pb(pLL(ta,le,se[i][a[i]].s,se[i][a[i]].t));
	}
	p.pb(ta);
	rep(i,p.size()-1){
		rep(j,n){
			if(iSSstrict(p[i],p[i+1],se[i][j].s,se[i][j].t)) return inf;
		}
	}
	return (le-ta).abs();
}
int main()
{
	Pt ta,le;
	rep(i,7){
		zyo[i][0]=1;
		rep(j,7) zyo[i][j+1]=zyo[i][j]*i;
	}
	int px,py,qx,qy,n;
	while(cin>>n,n){
		double ret=inf;
		rep(i,n){
			cin>>px>>py>>qx>>qy;
			se[0][i]=seg(Pt(px,py),Pt(qx,qy));
		}
		cin>>px>>py;ta=Pt(px,py);
		cin>>px>>py;le=Pt(px,py);
		rep(i,6) rep(j,zyo[n][i]){
			vector<int> a;int b=j;
			rep(k,i){a.pb(b%n);b/=n;}
			double ca=cal(a,n,ta,le);
			ret=min(ret,ca);
		}
		printf("%.12f\n",ret);
	}
}