/* * Input precision validator for NCPC 2013 problem "Cliff walk" * by Jaap Eldering, modified from solution. */ #include #include #include #include #include #include #include #include #include using namespace std; typedef vector VI; typedef vector VVI; typedef vector VD; typedef vector VVD; typedef vector VVVD; const int dx[4] = {1,0,-1,0}; const int dy[4] = {0,1,0,-1}; const int maxdz = 1000; const double sqsize = 10.0; const double eps = 2E-3; double a, m, a0, m0; int w,h,xs,ys; VVI height; VVVD reach; double dry(int z) { if ( z>=a ) return -2; return acos(2*z/a-1)*6/M_PI; } struct pos { int x,y; double t; pos() {} pos(int x_, int y_, double t_): x(x_), y(y_), t(t_) {} }; int operator <(pos a, pos b) { return a.t>b.t; } void finddist(pos start, int dir) { priority_queue que; que.push(start); while ( !que.empty() ) { pos curr = que.top(); que.pop(); if ( curr.t*m>12.0 ) break; if ( reach[curr.x][curr.y][dir]<=curr.t ) continue; reach[curr.x][curr.y][dir] = curr.t; // printf("reach %d,%d at %.4lf (dir=%d)\n",curr.x,curr.y,curr.t,dir); for(int d=0; d<4; d++) { pos next = curr; next.x += dx[d]; next.y += dy[d]; if ( next.x<0 || next.x>=w || next.y<0 || next.y>=h || abs(height[curr.x][curr.y]- height[next.x][next.y])>maxdz ) continue; double t = dry(height[next.x][next.y]); if ( dir==0 ) t += 1; if ( t>next.t ) next.t = t; next.t += m; // printf("next %d,%d at %.4lf (dir=%d)\n",next.x,next.y,next.t,dir); que.push(next); } } } int main() { cin >> a0 >> m0; cin >> w >> h >> xs >> ys; height = VVI(w,VI(h)); for(int y=0; y> height[x][y]; VI best(2,0); for(int epsdir=0; epsdir<2; epsdir++) { // test with +/-eps, use mm for height, hours for time: a = (a0+(epsdir==0 ? eps : -eps)) * 1000; m = (m0 * (1 + (epsdir==0 ? eps : -eps))) / 3600; reach = VVVD(w,VVD(h,VD(2,99.9))); for(int dir=0; dir<2; dir++) finddist(pos(xs,ys,0.0),dir); for(int y=0; ybest[epsdir] ) { // fprintf(stderr,"found best %d at %d,%d\n",d2,x,y); best[epsdir] = d2; } } } assert( best[0]==best[1] ); cout << setprecision(12) << sqsize*sqrt(best[0]) << endl; return 42; }