AOJ 2016: プールの監視員
2016年になってしまい仕方なく解いた。
と思ったら拍子抜けするほど簡単だった……ええ何これは……。
まあ確かに点列挙して最短路みたいな幾何問題は無限に練習したしなあ……。
#include<stdio.h> #include<algorithm> #include<math.h> #include<vector> #include<queue> using namespace std; const double EPS = 1e-10; const double INF = 1e+10; const double PI = acos(-1); Pt p[20]; Pt h[20]; double ijk[1100]; int v[1100]; int main(){ int a; while(scanf("%d",&a),a){ double tg,tw; for(int i=0;i<a;i++){ double X,Y; scanf("%lf%lf",&X,&Y); p[i]=Pt(X,Y); } p[a]=p[0]; scanf("%lf%lf",&tg,&tw); Pt s,t; double X,Y; scanf("%lf%lf",&X,&Y); s=Pt(X,Y); scanf("%lf%lf",&X,&Y); t=Pt(X,Y); double th=asin(tg/tw); for(int i=0;i<a;i++){ h[i]=hLP(p[i],p[i+1],t); } vector<Pt> hb; hb.push_back(s); hb.push_back(t); for(int i=0;i<a;i++){ hb.push_back(p[i]); } for(int i=0;i<a;i++){ for(int j=0;j<a;j++){ if(i==j||i==j+1)continue; Pt tmp=hLP(p[j],p[j+1],p[i]); double dist=(tmp-p[i]).ABS(); double len=dist*tan(th); Pt vec=p[j+1]-p[j]; vec=vec/(vec.ABS())*len; Pt t1=tmp+vec; Pt t2=tmp-vec; if(iSP(p[j],t1,p[j+1])==2)hb.push_back(t1); if(iSP(p[j],t2,p[j+1])==2)hb.push_back(t2); } } for(int j=0;j<a;j++){ Pt tmp=hLP(p[j],p[j+1],t); double dist=(tmp-t).ABS(); double len=dist*tan(th); Pt vec=p[j+1]-p[j]; vec=vec/(vec.ABS())*len; Pt t1=tmp+vec; Pt t2=tmp-vec; if(iSP(p[j],t1,p[j+1])==2)hb.push_back(t1); if(iSP(p[j],t2,p[j+1])==2)hb.push_back(t2); } for(int j=0;j<a;j++){ Pt tmp=hLP(p[j],p[j+1],s); double dist=(tmp-s).ABS(); double len=dist*tan(th); Pt vec=p[j+1]-p[j]; vec=vec/(vec.ABS())*len; Pt t1=tmp+vec; Pt t2=tmp-vec; if(iSP(p[j],t1,p[j+1])==2)hb.push_back(t1); if(iSP(p[j],t2,p[j+1])==2)hb.push_back(t2); } int sz=hb.size(); for(int i=0;i<sz;i++){ v[i]=0; ijk[i]=999999999; } ijk[0]=0; for(int i=0;i<sz;i++){ int at=0; double tmp=999999999; for(int j=0;j<sz;j++){ if(!v[j]&&tmp>ijk[j]){ at=j;tmp=ijk[j]; } } v[at]=1; for(int j=0;j<sz;j++){ if(v[j])continue; Pt M=(hb[at]+hb[j])/2; double toc=ijk[at]; if(sGP(a,p,M)==0)toc+=(hb[at]-hb[j]).ABS()*tg; else toc+=(hb[at]-hb[j]).ABS()*tw; ijk[j]=min(ijk[j],toc); } } //for(int i=0;i<sz;i++)printf("(%f %f): %f\n",hb[i].x,hb[i].y,ijk[i]); printf("%.12f\n",ijk[1]); } }