#include #include #include #include #include using namespace std; #define N 3002 #define eps 1e-8 #define inf 1e15 typedef complex P; namespace std { int operator<(const P& a, const P& b) { if (fabs(real(a)-real(b))>eps) return real(a)eps) return imag(a) > g[N]; map intern_tbl; int done[N]; double tbl[N]; int intern(P p) { if (intern_tbl.count(p)) return intern_tbl[p]; int res=intern_tbl.size(); intern_tbl[p]=res; return res; } int calc_x(int a, int b, double& res) { double y=imag(ps[a]); double x=real(ps[b]); double x0=real(ps[b]),x1=real(ps[b+1]); double y0=imag(ps[b]),y1=imag(ps[b+1]); if (fabs(y0-y1) nps; for (int i=0;ileft_x) left_x=x; if (x>real(ps[i])&&xeps) { P p(left_x,imag(ps[i])); int id0=intern(ps[i]); int id1=intern(p); double d=abs(ps[i]-p)/sd; g[id0].push_back(make_pair(id1,d)); g[id1].push_back(make_pair(id0,d)); nps.push_back(p); } if (right_x!=inf&&imag(ps[i+1])-imag(ps[i])>eps) { P p(right_x,imag(ps[i])); int id0=intern(ps[i]); int id1=intern(p); double d=abs(ps[i]-p)/sd; g[id0].push_back(make_pair(id1,d)); g[id1].push_back(make_pair(id0,d)); nps.push_back(p); } } sort(nps.begin(),nps.end()); for (int i=0;i<(int)nps.size()-1;++i) { int id0=intern(nps[i]); int id1=intern(nps[i+1]); double d=abs(nps[i+1]-nps[i])/sw; g[id0].push_back(make_pair(id1,d)); g[id1].push_back(make_pair(id0,d)); } int start=intern(ps[0]),goal=intern(ps[n-1]); multimap mm; mm.insert(make_pair(0,start)); tbl[start]=0; while(!mm.empty()) { double cost=mm.begin()->first; int pos=mm.begin()->second; mm.erase(mm.begin()); if (done[pos]) continue; done[pos]=1; if (pos==goal) break; for (int i=0;incost) { tbl[npos]=ncost; mm.insert(make_pair(ncost,npos)); } } } printf("%.6lf\n",tbl[goal]); } }