幾何してグラフ作って最短路というありがちなつまらないやつ。
線分が多角形に入ってるかどうかの判定も面倒で有名。
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]); } }
