PKU 1556 The Doors
http://poj.org/problem?id=1556
壁がある部屋の端から端までの最短距離を求めろというような問題。
幾何なので面倒臭がって開く度に放置していた問題。
やってみると誤差とか全然考慮してなくても通るっぽいので、そこまで面倒じゃないような気がします。
int n; double x[30],y[30][4]; bool vis[30][4]; bool can(PI a,PI b){ double ax=x[a.F],bx=x[b.F]; double ay=y[a.F][a.S],by=y[b.F][b.S]; for(int i=a.F+1;i<b.F;++i){ double cy=(ay-by)*(x[i]-bx)/(ax-bx)+by; if(0<=cy && cy<=y[i][0] || y[i][1]<=cy && cy<=y[i][2] || y[i][3]<=cy && cy<=10)return false; } return true; } void solve(){ x[0]=0; rep(i,4)y[0][i]=5; x[n+1]=10; rep(i,4)y[n+1][i]=5; rep(i,n){ cin>>x[i+1]; rep(j,4)cin>>y[i+1][j]; } priority_queue<pair<double,PI> >q; memset(vis,0,sizeof(vis)); q.push(mp(0,mp(0,0))); while(!q.empty()){ double cc=-q.top().F; PI cv=q.top().S; q.pop(); if(vis[cv.F][cv.S])continue; //cout<<cc<<' '<<cv.F<<' '<<cv.S<<endl; vis[cv.F][cv.S]=true; if(cv.F==n+1){ printf("%.2f\n",cc); return; } for(int i=cv.F+1;i<=n+1;++i){ rep(j,4) if(can(cv,mp(i,j))){ double tx=x[i]-x[cv.F]; double ty=y[cv.F][cv.S]-y[i][j]; q.push(mp(-cc-sqrt(tx*tx+ty*ty),mp(i,j))); } } } } main(){ while(cin>>n,~n) solve(); }