题目链接 ：http://acm.hdu.edu.cn/showproblem.php?pid=6670
Mindis
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 548 Accepted Submission(s): 119
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
对于每组数据，输出一个小数表示答案。答案保留 5 位小数。
Sample Input
1
1
5 5 6 6
7 7 8 8
Sample Output
2.00000
Source
2019 年百度之星·程序设计大赛 - 初赛一
思路：
先把题目中给出的所有点离散化一下，得到一个n*m 的网格，n和m最大都是400
我们枚举每一个矩形，同时枚举离散化之后的矩形坐标中包括哪些点，
这样能维护出每一个点被多少个矩形包括，
cnt[x][y][k] 表示网格上横坐标为x，纵坐标为y，方向为k，（0，1，2，3代表上下左右）这条离散化后长度为1的边被矩形覆盖的次数。
然后相邻的点建边（边的代价为距离/速度，即时间，距离我们可以通过坐标减去得出，速度由该点被多少个矩形包括得出），跑图的最短路径即可，
代码写起来很长，其实不难写，因为写很多部分是不需要动脑的机械操作。，注意细节即可，
细节见代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
inline void getInt(int* p);
const int maxn = 400010;
const ll inf = 1e18;
/*** TEMPLATE CODE * * STARTS HERE ***/
int t;
int n;
struct juzhen
{
int x1,x2,y1,y2;
}a[500];
std::vector<int> vx,vy;
int sn,sm;
int getid(int x,int y)
{
return (x-1)*sn+y;
}
double dis[maxn];
struct node
{
int to;
double val;
node (){}
node(int tt,double vv)
{
to=tt;
val=vv;
}
bool operator <(const node &b)const
{
return val>b.val;
}
};
std::vector<node> v[maxn];
int cnt[500][500][5];
bool check(int x,int y)
{
return x>=1&&x<=sn&&y>=1&&y<=sm;
}
juzhen aid;
priority_queue<node> heap;
void dij()
{
while(heap.size())
{
heap.pop();
}
dis[getid(aid.x1,aid.y1)]=0;
heap.push(node(getid(aid.x1,aid.y1),0));
node temp;
while(!heap.empty())
{
temp=heap.top();
heap.pop();
for(auto x:v[temp.to])
{
if(dis[x.to]>x.val+dis[temp.to])
{
dis[x.to]=x.val+dis[temp.to];
heap.push(node(x.to,dis[x.to]));
}
}
}
}
int main()
{
//freopen("D:\\code\\text\\input.txt","r",stdin);
//freopen("D:\\code\\text\\output.txt","w",stdout);
gbtb;
cin>>t;
while(t--)
{
cin>>n;
vx.clear();
vy.clear();
repd(i,1,n)
{
cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
vx.push_back(a[i].x1);
vx.push_back(a[i].x2);
vy.push_back(a[i].y1);
vy.push_back(a[i].y2);
}
cin>>aid.x1>>aid.y1>>aid.x2>>aid.y2;
vx.push_back(aid.x1);
vx.push_back(aid.x2);
vy.push_back(aid.y1);
vy.push_back(aid.y2);
sort(ALL(vx));
sort(ALL(vy));
vx.erase(unique(ALL(vx)),vx.end());
vy.erase(unique(ALL(vy)),vy.end());
sn=sz(vx);
sm=sz(vy);
repd(i,1,sn)
{
repd(j,1,sm)
{
dis[getid(i,j)]=inf;
v[getid(i,j)].clear();
repd(z,0,3)
cnt[i][j][z]=1;
}
}
aid.x1=lower_bound(ALL(vx),aid.x1)-vx.begin()+1;
aid.x2=lower_bound(ALL(vx),aid.x2)-vx.begin()+1;
aid.y1=lower_bound(ALL(vy),aid.y1)-vy.begin()+1;
aid.y2=lower_bound(ALL(vy),aid.y2)-vy.begin()+1;
repd(i,1,n)
{
int x1=lower_bound(ALL(vx),a[i].x1)-vx.begin()+1;
int y1=lower_bound(ALL(vy),a[i].y1)-vy.begin()+1;
int x2=lower_bound(ALL(vx),a[i].x2)-vx.begin()+1;
int y2=lower_bound(ALL(vy),a[i].y2)-vy.begin()+1;
repd(j,x1+1,x2-1)
{
repd(k,y1+1,y2-1)
{
repd(z,0,3)
cnt[j][k][z]++;
}
}
// 0 1 2 3
// 上 下 左 右
repd(j,x1+1,x2-1)
{
cnt[j][y2][1]++;
cnt[j][y2][2]++;
cnt[j][y2][3]++;
cnt[j][y1][0]++;
cnt[j][y1][2]++;
cnt[j][y1][3]++;
}
repd(j,y1+1,y2-1)
{
cnt[x1][j][0]++;
cnt[x1][j][1]++;
cnt[x1][j][3]++;
cnt[x2][j][0]++;
cnt[x2][j][1]++;
cnt[x2][j][2]++;
}
cnt[x1][y1][0]++;
cnt[x1][y1][3]++;
cnt[x2][y1][0]++;
cnt[x2][y1][2]++;
cnt[x1][y2][3]++;
cnt[x1][y2][1]++;
cnt[x2][y2][1]++;
cnt[x2][y2][2]++;
}
repd(i,1,sn)
{
repd(j,1,sm)
{
if(check(i-1,j))
{
v[getid(i,j)].push_back(node(getid(i-1,j),1.00*(vx[i-1]-vx[i-2])/cnt[i][j][2]));
}
if(check(i+1,j))
{
v[getid(i,j)].push_back(node(getid(i+1,j),1.00*(vx[i]-vx[i-1])/cnt[i][j][3]));
}
if(check(i,j-1))
{
v[getid(i,j)].push_back(node(getid(i,j-1),1.00*(vy[j-1]-vy[j-2])/cnt[i][j][1]));
}
if(check(i,j+1))
{
v[getid(i,j)].push_back(node(getid(i,j+1),1.00*(vy[j]-vy[j-1])/cnt[i][j][0]));
}
}
}
dij();
// cout<<getid(aid.x2,aid.y2)<<endl;
cout<<fixed<<setprecision(5)<<dis[getid(aid.x2,aid.y2)]<<endl;
}
return 0;
}
inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
}
else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}
京公网安备 11010502036488号