A17496. 能量护盾
填空题
困难
知识点
题目描述
能量护盾
题目描述
在一处被宇宙射线笼罩的星域中，你驾驶着一艘小型探索飞船，需要从坐标 (xs,ys) 航行到坐标 (xt,yt)。
飞船可以以速度 1 向任意方向移动，自身视为一个点。
星域中分布着 N 个圆形能量护盾，第 i 个护盾的圆心为 (xi,yi)，半径为 ri。护盾之间可能相互重叠，也可能存在包含关系。
飞船一旦进入某个护盾的内部，就能免受宇宙射线的伤害。若一个点不在任何护盾内部，则飞船会持续受到宇宙射线的照射。
你的目标是：在从起点到终点的航行过程中，尽可能减少受到宇宙射线照射的总时间。
请你计算这个最小照射时间。
输入格式
第一行，四个整数 xs,ys,xt,yt，分别表示起点和终点的坐标。
第二行，一个整数 N，表示圆形护盾的数量。
接下来 N 行，每行三个整数 xi,yi,ri，描述第 i 个护盾的圆心坐标和半径。
输出格式
输出一个实数，表示受到宇宙射线照射的最小时间，保留 10 位小数。
输入样例#1
-2 -2 2 2
1
0 0 1输出样例#1
3.6568542495输入样例#2
-2 0 2 0
2
-1 0 2
1 0 2输出样例#2
0.0000000000输入样例#3
4 -2 -2 4
3
0 0 2
4 0 1
0 4 1输出样例#3
4.0000000000说明提示
−109≤xs,ys,xt,yt≤109
(xs,ys)≠(xt,yt)
1≤N≤1000
−109≤xi,yi≤109
1≤ri≤109
参考答案
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef long long ll;
const double INF = 1e18;
const double eps = 1e-8;
struct Point {
ll x, y;
Point() {}
Point(ll x_, ll y_) : x(x_), y(y_) {}
};
struct Circle {
ll x, y, r;
Circle() {}
Circle(ll x_, ll y_, ll r_) : x(x_), y(y_), r(r_) {}
};
// 两点距离
double dis_pp(const Point& a, const Point& b) {
ll dx = a.x - b.x;
ll dy = a.y - b.y;
return sqrt(1.0 * dx * dx + 1.0 * dy * dy);
}
// 点到圆的暴露长度，点在圆内返回0
double dis_pc(const Point& p, const Circle& c) {
double d = dis_pp(p, Point(c.x, c.y));
if (d <= c.r + eps) return 0.0;
return d - c.r;
}
// 两个圆之间暴露长度，相交/包含返回0
double dis_cc(const Circle& a, const Circle& b) {
double d = dis_pp(Point(a.x, a.y), Point(b.x, b.y));
double sumr = a.r + b.r;
if (d <= sumr + eps) return 0.0;
return d - sumr;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(10);
ll xs, ys, xt, yt;
cin >> xs >> ys >> xt >> yt;
Point S(xs, ys), T(xt, yt);
int N;
cin >> N;
vector<Circle> cir(N);
for (int i = 0; i < N; i++) {
cin >> cir[i].x >> cir[i].y >> cir[i].r;
}
// 总点数：0起点，1~N护盾，N+1终点
int tot = N + 2;
vector<vector<double>> g(tot, vector<double>(tot, INF));
for (int i = 0; i < tot; i++) g[i][i] = 0;
// 0(S) <-> N+1(T)
g[0][N+1] = dis_pp(S, T);
g[N+1][0] = dis_pp(S, T);
// 0(S) 和所有护盾 1~N
for (int i = 1; i <= N; i++) {
double d = dis_pc(S, cir[i-1]);
g[0][i] = d;
g[i][0] = d;
}
// N+1(T) 和所有护盾 1~N
for (int i = 1; i <= N; i++) {
double d = dis_pc(T, cir[i-1]);
g[N+1][i] = d;
g[i][N+1] = d;
}
// 护盾之间 i,j (1~N)
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
double d = dis_cc(cir[i-1], cir[j-1]);
g[i][j] = d;
g[j][i] = d;
}
}
// Floyd 求全源最短路，N<=1000 tot=1002，1e9？不行！换Dijkstra单源
vector<double> dist(tot, INF);
vector<bool> vis(tot, false);
dist[0] = 0;
for (int step = 0; step < tot; step++) {
int u = -1;
double minv = INF;
for (int i = 0; i < tot; i++) {
if (!vis[i] && dist[i] < minv) {
minv = dist[i];
u = i;
}
}
if (u == -1) break;
vis[u] = true;
for (int v = 0; v < tot; v++) {
if (g[u][v] < INF && dist[v] > dist[u] + g[u][v]) {
dist[v] = dist[u] + g[u][v];
}
}
}
cout << dist[N+1] << endl;
return 0;
}
上一题
下一题