Problem Description

平面上有?n?個矩形，矩形的邊平行于坐標軸，現在度度熊需要操控一名角色從?A?點走到?B點。?
該角色可以上下左右移動，在恰被?k?個矩形覆蓋的區域，該角色的速率為?k+1?個距離/秒（矩形覆蓋區域包括邊界）。?

請求出?A?移動到 B 最快需要多少秒。

Input

第一行一個整數 T (1≤T≤5) 表示數據組數。?
對于每組數據，第一行輸入一個整數 n (1≤n≤200)。?
接下來 n 行每行 4 個整數 x1,y1,x2,y2 (0≤x1<x2≤1000000000,0≤y1<y2≤1000000000)，分別表示矩形的左下角和右上角的坐標。?
最后一行四個整數 xa,ya,xb,yb ((0≤xa,xb,ya,yb≤1000000000) 代表 A 和 B 的坐標。

Output

出 T 行，每行一個整數表示答案。對于每組數據，輸出一個小數表示答案。答案保留 5 位小數。

Sample Input

1
1
5 5 6 6
7 7 8 8

Sample Output

2.00000

思路：

題中給出的 x、y 的范圍可到?1000000000，但矩形個數 n 最多直到 200，因此可以用區間離散化的思想，將所有的 x、y 的坐標保存后離散化，建立網格圖，這樣一來，最多只有 400*400=160000 個點，相鄰兩點的邊就是兩點之間的距離/速度

然后開兩個數組，分別統計每個點在水平和垂直方向上被多少個矩形覆蓋，對于每一個矩形，將每一條邊被矩形覆蓋的次數賦給其臨近的點，這樣將矩形內部的速度轉為兩點之間的速度，最后跑最短路即可

Source Program

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const int MOD = 1E9+7; const int N = 400+5; const int dx[] = {1,-1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;double dis[N][N]; bool vis[N][N]; struct Node{int x,y;bool operator < (const Node &rhs) const{return dis[x][y]>=dis[rhs.x][rhs.y];} }node[N],st,ed; int G[N][5]; int x[N],y[N],totX,totY; int numY[N][N],numX[N][N];//水平與垂直方向每個頂點被矩形覆蓋的距離 void bfs(int lenX,int lenY){for(int i=1;i<=lenX;i++){for(int j=1;j<=lenY;j++){dis[i][j]=INF;vis[i][j]=false;}}dis[st.x][st.y]=0;priority_queue<Node,vector<Node>,less<Node> >Q;Q.push(st);while(!Q.empty()){Node now=Q.top();Q.pop();int nowX=now.x;int nowY=now.y;if(vis[nowX][nowY])continue;vis[nowX][nowY]=true;for(int i=0;i<4;i++){int nx=nowX+dx[i];int ny=nowY+dy[i];if(nx>totX||ny>totY||!nx||!ny||vis[nx][ny])continue;double temp;if(nowX==nx)//垂直方向temp = abs(y[nowY]-y[ny])*1.0 / numY[nowX][min(nowY,ny)];else//水平方向temp = abs(x[nowX]-x[nx])*1.0 / numX[min(nowX,nx)][nowY];if(dis[nowX][nowY]+temp<dis[nx][ny]){dis[nx][ny]=dis[nowX][nowY]+temp;now.x=nx;now.y=ny;Q.push(now);}}} } int main(){int t;scanf("%d",&t);while(t--){int n;scanf("%d",&n);totX=0,totY=0;for(int i=1;i<=n;i++){for(int j=1;j<=4;j++)scanf("%d",&G[i][j]);x[++totX]=G[i][1];y[++totY]=G[i][2];x[++totX]=G[i][3];y[++totY]=G[i][4];}scanf("%d%d%d%d",&st.x,&st.y,&ed.x,&ed.y);x[++totX]=st.x;y[++totY]=st.y;x[++totX]=ed.x;y[++totY]=ed.y;//離散化sort(x+1,x+1+totX);sort(y+1,y+1+totY);int lenX=unique(x+1,x+1+totX)-x-1;int lenY=unique(y+1,y+1+totY)-y-1;for(int i=1;i<=n;i++){G[i][1]=lower_bound(x+1,x+1+lenX,G[i][1])-x;G[i][2]=lower_bound(y+1,y+1+lenY,G[i][2])-y;G[i][3]=lower_bound(x+1,x+1+lenX,G[i][3])-x;G[i][4]=lower_bound(y+1,y+1+lenY,G[i][4])-y;}st.x=lower_bound(x+1,x+1+lenX,st.x)-x;st.y=lower_bound(y+1,y+1+lenY,st.y)-y;ed.x=lower_bound(x+1,x+1+lenX,ed.x)-x;ed.y=lower_bound(y+1,y+1+lenY,ed.y)-y;//統計每個點被矩形覆蓋次數for(int i=1;i<=lenX;i++)for(int j=1;j<=lenY;j++)numX[i][j]=numY[i][j]=1;for(int i=1;i<=n;i++){//水平方向for(int j=G[i][1];j<G[i][3];j++)//最右端不記錄for(int k=G[i][2];k<=G[i][4];k++)numX[j][k]++;//垂直方向for(int j=G[i][1];j<=G[i][3];j++)for(int k=G[i][2];k<G[i][4];k++)//最右端不記錄numY[j][k]++;}bfs(lenX,lenY);printf("%.5lf\n",dis[ed.x][ed.y]);}return 0; }

總結

以上是生活随笔為你收集整理的Mindis（HDU-6670）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。