MirrorLabyrinth (AOJ2514)
まあやるだけ・・・
(凸とは限らない)多角形2つのcapでできる多角形?上での最短路 を求めようとするときに,実は元の多角形の頂点しかいらない というのはそんなに自明ではない気がする(いや言われたらわかるんだけど,言われずに思いつくもんだろうか)
あとは多角形と線分の包含も、頑張ればO(N)でできそうなものの闇ケースがもりもり出てくるため交点と中点求めて全部点内包判定するのが無難.
この方法だと多角形の自己接触ありだとしても解けるから嬉しいですね.
#include <bits/stdc++.h> #define rep(i,n) for(int i=0;i<(int)(n);i++) #define rep1(i,n) for(int i=1;i<=(int)(n);i++) #define all(c) c.begin(),c.end() #define pb push_back #define fs first #define sc second #define show(x) cout << #x << " = " << x << endl #define chmin(x,y) x=min(x,y) #define chmax(x,y) x=max(x,y) using namespace std; typedef double D; typedef complex<D> P; typedef pair<P,P> L; typedef vector<P> Pol; D eps=1e-9,inf=1e9; int A,n[100]; Pol pol[100]; P s,t; L l; bool eq(D a,D b){return abs(a-b)<eps;} int sig(D a){return eq(a,0)?0:(a>0?1:-1);} D cro(P a,P b){return imag(conj(a)*b);} D dot(P a,P b){return real(conj(a)*b);} int ccw(P a,P b,P c){ if(sig(cro(b-a,c-a))==1) return 1; if(sig(cro(b-a,c-a))==-1) return -1; if(eq(abs(a-c)+abs(c-b),abs(a-b))) return 0; if(eq(abs(a-b)+abs(c-b),abs(a-c))) return -2; return 2; } int ccw(L a,P p){return ccw(a.fs,a.sc,p);} P intLL(L a,L b){ D t=cro(a.sc-a.fs,a.sc-b.fs)/cro(a.sc-a.fs,b.sc-b.fs); return b.fs+t*(b.sc-b.fs); } bool contain(Pol pol,P p){ bool in=0; int N=pol.size(); rep(i,N){ P a=pol[i]-p,b=pol[(i+1)%N]-p; if(ccw(a,b,P(0,0))==0) return 1; if(imag(a)>imag(b)) swap(a,b); if(sig(imag(a))<=0&&0<sig(imag(b))&&ccw(P(0,0),a,b)==1) in=!in; } return in; } P perp(L l,P p){ D t=dot(p-l.fs,l.fs-l.sc)/norm(l.fs-l.sc); return l.fs+t*(l.fs-l.sc); } P refl(L l,P p){ return p+2.0*(perp(l,p)-p); } bool ispal(L a,L b){ return sig(cro(a.fs-a.sc,b.fs-b.sc))==0; } bool iSS(L a,L b){ return ccw(a,b.fs)*ccw(a,b.sc)<=0&&ccw(b,a.fs)*ccw(b,a.sc)<=0; } L BL; bool compBL(const P& a,const P& b){ //BL上の点をソート(BL.fs側が小さい) return dot(l.sc-l.fs,a-l.fs)<dot(l.sc-l.fs,b-l.fs); } bool containE(Pol pol,L l){ vector<P> ps; ps.pb(l.fs); ps.pb(l.sc); int N=pol.size(); rep(i,N){ L a(pol[i],pol[(i+1)%N]); if(ispal(a,l)) continue; if(!ispal(a,l)&&iSS(a,l)) ps.pb(intLL(a,l)); } BL=l; sort(all(ps),compBL); int K=ps.size(); rep(i,K-1) ps.pb((ps[i]+ps[i+1])/2.0); for(P p:ps) if(!contain(pol,p)) return 0; return 1; } int main(){ while(true){ cin>>A; if(A==0) break; rep(i,A){ pol[i].clear(); cin>>n[i]; rep(j,n[i]){ int x,y; cin>>x>>y; pol[i].pb(P(x,y)); } } { int a,b,c,d; cin>>a>>b>>c>>d; s=P(a,b),t=P(c,d); cin>>a>>b>>c>>d; l=L(P(a,b),P(c,d)); } int a=-1,b=-1,c=-1,d=-1; rep(i,A){ if(contain(pol[i],s)) a=i; if(contain(pol[i],t)) b=i; if(contain(pol[i],refl(l,s))) c=i; if(contain(pol[i],refl(l,t))) d=i; } if(a<0||b<0||c<0||d<0||a!=b||c!=d){ puts("impossible"); continue; } Pol e=pol[a],f=pol[c]; int E=e.size(),F=f.size(); rep(i,F/2) swap(f[i],f[F-1-i]); rep(i,F) f[i]=refl(l,f[i]); Pol ps; ps.pb(s); ps.pb(t); for(P p:e) ps.pb(p); for(P p:f) ps.pb(p); int N=ps.size(); D dis[102][102]={}; rep(i,N) rep(j,N) if(i!=j){ dis[i][j]=inf; if(containE(e,L(ps[i],ps[j]))&&containE(f,L(ps[i],ps[j]))) dis[i][j]=abs(ps[i]-ps[j]); } rep(i,N) rep(j,N) rep(k,N) chmin(dis[j][k],dis[j][i]+dis[i][k]); if(dis[0][1]==inf) puts("impossible"); else printf("%.12f\n",dis[0][1]); } }