AOJ 2246: Alice and Bomb

ついにdiffを埋めた！

かつてのPCKの最終防衛幾何によくあった、ライブラリの強さが大事な問題。
強力なライブラリでごり押しがきくので、思ったより楽だった。

行きたい区画は線分とするとよい。経由する点で最短路を求めて、点からその線分に行くということにするとうまく書ける。

// ライブラリとインクルード略
vector<Pt>p[110];
vector<Pt>q;
vector<pair<Pt,Pt> > edge;
double ijk[110000];
int v[110000];
int main(){
	int a;
	while(scanf("%d",&a),a){
		double bx,by;scanf("%lf%lf",&bx,&by);
		Pt bm=Pt(bx,by);
		for(int i=0;i<a;i++)p[i].clear();
		for(int i=0;i<a;i++){
			int c;scanf("%d",&c);
			for(int j=0;j<c;j++){
				double ix,iy;
				scanf("%lf%lf",&ix,&iy);
				p[i].push_back(Pt(ix,iy));
			}
		}
		bool zr=false;
		for(int i=0;i<a;i++){
			for(int j=0;j<p[i].size();j++){
				if(iSSstrict(p[i][j],p[i][(j+1)%p[i].size()],Pt(0,0),bm))zr=true;
			}
		}
		if(zr){
			printf("%.12f\n",0.0);
			continue;
		}
		q.clear();
		edge.clear();
		q.push_back(Pt(0,0));
		for(int i=0;i<a;i++){
			for(int j=0;j<p[i].size();j++){
				Pt r=bm+(p[i][j]-bm)*1000000;
				bool tc=false;
				for(int k=0;k<a;k++)for(int l=0;l<p[k].size();l++){
					if(iSSstrict(p[k][l],p[k][(l+1)%p[k].size()],p[i][j],r)){
						r=pLL(p[k][l],p[k][(l+1)%p[k].size()],p[i][j],r);
					}
					if(iSSstrict(p[k][l],p[k][(l+1)%p[k].size()],bm,p[i][j])){
						tc=true;break;
					}
				}
				if(tc)continue;
				q.push_back(p[i][j]);
				if(r.ABS()<100000)q.push_back(r);
				if(!iGSstrict(p[i],p[i][j],r))edge.push_back(make_pair(p[i][j],r));
			}
		}
		
		int n=q.size();
		for(int i=0;i<n;i++)ijk[i]=999999999;
		for(int i=0;i<n;i++)v[i]=0;
		ijk[0]=0;
		for(int i=0;i<n;i++){
			double best=99999999;
			int at=-1;
			for(int j=0;j<n;j++){
				if(!v[j]&&best>ijk[j]){
					best=ijk[j];
					at=j;
				}
			}
			if(!~at)break;
			v[at]=1;
			for(int j=0;j<n;j++){
				if(v[j]||ijk[at]+(q[at]-q[j]).ABS()+EPS>ijk[j])continue;
				bool ok=true;
				for(int k=0;k<a;k++){
					if(iGSstrict(p[k],q[at],q[j])){ok=false;break;}
				}
				if(ok){
					ijk[j]=min(ijk[j],ijk[at]+(q[at]-q[j]).ABS());
				}
			}
		}
		double ret=999999999;
		//for(int i=0;i<edge.size();i++)printf("(%f %f), (%f %f)\n",edge[i].first.x,edge[i].first.y,edge[i].second.x,edge[i].second.y);
		for(int i=0;i<n;i++){
			for(int j=0;j<edge.size();j++){
				Pt L=edge[j].first;
				Pt R=edge[j].second;
				Pt H=hLP(edge[j].first,edge[j].second,q[i]);
				bool ok;
				ok=true;
				if(ret<EPS+ijk[i]+(q[i]-L).ABS())ok=false;
				for(int k=0;ok&&k<a;k++)if(iGSstrict(p[k],q[i],L)){ok=false;break;}
				if(ok)ret=min(ret,ijk[i]+(q[i]-L).ABS());
				ok=true;
				if(ret<EPS+ijk[i]+(q[i]-R).ABS())ok=false;
				for(int k=0;ok&&k<a;k++)if(iGSstrict(p[k],q[i],R)){ok=false;break;}
				if(ok)ret=min(ret,ijk[i]+(q[i]-R).ABS());
				ok=true;
				if(ret<EPS+ijk[i]+(q[i]-H).ABS())ok=false;
				for(int k=0;ok&&k<a;k++)if(iGSstrict(p[k],q[i],H)){ok=false;break;}
				if(ok&&iSP(L,H,R)==2){
					ret=min(ret,ijk[i]+(q[i]-H).ABS());
				}
			}
		}
		printf("%.12f\n",ret);
	}
}