#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i,n) for(int _n=(n),i=0; i<_n; ++i) #define FOR(i,a,b) for(int _b=(b),i=(a); i<=_b; ++i) #define FORD(i,a,b) for(int _b=(b),i=(a); i>=_b; --i) #define FORE(i,a) for(VAR(i,a.begin()); i!=a.end(); ++i) #define PB push_back #define BEG begin() #define END end() #define SZ size() #define MP make_pair #define F first #define S second #define D double #define LL long long #define LD long double #define VI vector #define Cell pair #define Interval pair #define MAX 500 #define INF (LD)1000*1000 LD pi=(LD)2.0*acosl(0); LD height[MAX][MAX]; LD flood[MAX][MAX]; LD deflood[MAX][MAX]; LD a,m; int X,Y,W,H; vector > dir; vector > graph[MAX][MAX]; vector > graph_rev[MAX][MAX]; LD vis[MAX][MAX]; LD vis_rev[MAX][MAX]; LD flooding_time(LD h){ if (h>a) return (LD)-1000.0; return ((LD)6.0/pi)*acosl(((LD)2.0*h)/a - (LD)1.0); } pair try_arc(Cell a, Cell b){ if (fabsl(height[a.F][a.S]-height[b.F][b.S])>(LD)1.0) return MP(1,MP(0.0,0.0)); LD lower=max(flood[a.F][a.S]+(LD)1.0,flood[b.F][b.S]+(LD)1.0); LD upper=min(deflood[a.F][a.S]-m,deflood[b.F][b.S]-m); if (lower>upper) return MP(1,MP(0.0,0.0)); else return MP(0,MP(lower,upper)); } void compute_flood(){ REP(i,H+1) REP(j,W+1){ vis[i][j]=INF; vis_rev[i][j]=-INF; flood[i][j]=flooding_time(height[i][j]); deflood[i][j]=(LD)12.0 - flood[i][j]; } } void build_graph(){ FOR(i,1,H) FOR(j,1,W) REP(t,4){ pair q=try_arc(MP(i,j),MP(i+dir[t].F,j+dir[t].S)); if (q.F) continue; graph[i][j].PB(MP(MP(i+dir[t].F,j+dir[t].S),q.S)); graph_rev[i+dir[t].F][j+dir[t].S].PB(MP(MP(i,j),q.S)); } } priority_queue > q; void dijkstra(){ q=priority_queue >(); q.push(MP(0.0,MP(X,Y))); while(!q.empty()){ pair event = q.top(); q.pop(); LD t=-event.F; int x=event.S.F, y=event.S.S; // printf("%d %d %Lf %Lf\n",x,y,t,vis[x][y]); if (vis[x][y]<=t) continue; vis[x][y]=t; REP(k,graph[x][y].size()){ int xp=graph[x][y][k].F.F; int yp=graph[x][y][k].F.S; if (vis[xp][yp]upper) continue; LD reach_time=max(t,lower)+m; q.push(MP(-reach_time,MP(xp,yp))); } } } void dijkstra_rev(){ q=priority_queue >(); q.push(MP(12.0,MP(X,Y))); while(!q.empty()){ pair event = q.top(); q.pop(); LD t=event.F; int x=event.S.F, y=event.S.S; if (vis_rev[x][y]>=t) continue; vis_rev[x][y]=t; REP(k,graph_rev[x][y].size()){ int xp=graph_rev[x][y][k].F.F; int yp=graph_rev[x][y][k].F.S; if (vis_rev[xp][yp]>-INF+(LD)1.0) continue; LD lower=graph_rev[x][y][k].S.F; LD upper=graph_rev[x][y][k].S.S; if (t