AOJ 2514: MirrorLabyrinth

幾何してグラフ作って最短路というありがちなつまらないやつ。
線分が多角形に入ってるかどうかの判定も面倒で有名。
550なのに心が折れそうになった。というかこれはこんな問題で心が折れそうになる最近の自分が悪いと思う。

だけど550の実装量じゃないよね。

#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<vector>
using namespace std;
// FHC楽しかったような気がするのでいつか参加記かきます。
vector<Pt>poly[110];
vector<Pt>hb;
double ijk[11000];
int v[11000];
bool iGSstrict(int t, Pt a, Pt b) {
	for(int i=0;i<poly[t].size();i++){
		if(iLL(a,b,poly[t][i],poly[t][(i+1)%poly[t].size()])==-1)continue;
		if(iSSstrict(a,b,poly[t][i],poly[t][(i+1)%poly[t].size()]))return 1;
	}
	vector<Pt>tmp;
	for(int i=0;i<poly[t].size();i++){
		if(iLL(a,b,poly[t][i],poly[t][(i+1)%poly[t].size()])==-1)continue;
		if(iSS(a,b,poly[t][i],poly[t][(i+1)%poly[t].size()])){
			tmp.push_back(pLL(a,b,poly[t][i],poly[t][(i+1)%poly[t].size()]));
		}
	}
	tmp.push_back(a);
	tmp.push_back(b);
	//if(sGP(poly[t].size(),poly[t],(a*0.99999+b*0.00001))==-1)return 1;
	//if(sGP(poly[t].size(),poly[t],(b*0.99999+a*0.00001))==-1)return 1;
	std::sort(tmp.begin(),tmp.end());
	for(int i=1;i<tmp.size();i++){
		Pt M=(tmp[i-1]+tmp[i])/2;
		if(sGP(poly[t].size(),poly[t],M)==-1)return 1;
	}
//	printf("%d (%f %f) -> (%f %f)\n",t,a.x,a.y,b.x,b.y);
	return 0;
}
int main(){
	int a;
	while(scanf("%d",&a),a){
		for(int i=0;i<110;i++)poly[i].clear();
		for(int i=0;i<a;i++){
			int b;scanf("%d",&b);
			for(int j=0;j<b;j++){
				double X,Y;
				scanf("%lf%lf",&X,&Y);
				poly[i].push_back(Pt(X,Y));
			}
		}
		double X1,Y1,X2,Y2;
		scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
		Pt S1=Pt(X1,Y1);
		Pt G1=Pt(X2,Y2);
		scanf("%lf%lf%lf%lf",&X1,&Y1,&X2,&Y2);
		Pt L1=Pt(X1,Y1);
		Pt L2=Pt(X2,Y2);
		Pt S2=tLP(L1,L2,S1);
		Pt G2=tLP(L1,L2,G1);
		int f1=-1;
		int f2=-1;
		int t1=-1;
		int t2=-1;
		for(int i=0;i<a;i++){
			int n=poly[i].size();
			if(~sGP(n,poly[i],S1))f1=i;
			if(~sGP(n,poly[i],S2))f2=i;
			if(~sGP(n,poly[i],G1))t1=i;
			if(~sGP(n,poly[i],G2))t2=i;
		}
		if(f1==-1||f2==-1||t1==-1||t2==-1||f1!=t1||f2!=t2){
			printf("impossible\n");continue;
		}
		hb.clear();
		for(int i=0;i<poly[f1].size();i++)hb.push_back(poly[f1][i]);
		for(int i=0;i<poly[f2].size();i++)hb.push_back(tLP(L1,L2,poly[f2][i]));
	/*	for(int i=0;i<poly[f1].size();i++){
			for(int j=0;j<poly[f2].size();j++){
				Pt v1=tLP(L1,L2,poly[f2][j]);
				Pt v2=tLP(L1,L2,poly[f2][(j+1)%poly[f2].size()]);
				if(iSSstrict(poly[f1][i],poly[f1][(i+1)%poly[f1].size()],v1,v2)){
					hb.push_back(pLL(poly[f1][i],poly[f1][(i+1)%poly[f1].size()],v1,v2));
				}
			}
		}*/
		int S=hb.size();
		hb.push_back(S1);
		int T=hb.size();
		hb.push_back(G1);
		int sz=hb.size();
		for(int i=0;i<11000;i++){
			ijk[i]=999999999;v[i]=0;
		}
		ijk[S]=0;
	//	for(int i=0;i<sz;i++)printf("%f %f\n",hb[i].x,hb[i].y);
		for(int i=0;i<sz;i++){
			double dist=99999999;
			int at=-1;
			for(int j=0;j<sz;j++){
				if(!v[j]&&ijk[j]<dist){
					dist=ijk[j];
					at=j;
				}
			}
			if(!~at)break;
		//	printf("%f %f: %f\n",hb[at].x,hb[at].y,ijk[at]);
			v[at]=1;
			Pt from1=hb[at];
			Pt from2=tLP(L1,L2,hb[at]);
			for(int j=0;j<sz;j++){
				if(v[j])continue;
				if(ijk[j]<dist+(from1-hb[j]).ABS())continue;
				Pt to1=hb[j];
				Pt to2=tLP(L1,L2,to1);
		//		printf("%f %f %f %f\n",from1.x,from1.y,from2.x,from2.y);
				if(iGSstrict(f1,from1,to1)){
			//		printf("(%f %f) -> (%f %f): hit on 1\n",from1.x,from1.y,to1.x,to1.y);
					continue;
				}
				if(iGSstrict(f2,from2,to2)){
			//		printf("(%f %f) -> (%f %f): hit on 2\n",from1.x,from1.y,to1.x,to1.y);
					continue;
				}
				ijk[j]=dist+(from1-hb[j]).ABS();
			}
		}
		if(ijk[T]>99999999)printf("impossible\n");
		else printf("%.12f\n",ijk[T]);
	}
}