题解：AT_arc064_c [ARC064E] Cosmic Rays

jiangby2011 · 2025-10-06 02:02:43 · 题解

有趣的题目！

首先考虑你已经在一个屏障的圆形范围之内，现在要去到下一个屏障的范围要走的最短距离。

你发现在这个屏障的范围之内可以随便的移动，所以这个问题的答案就是两个圆上各取一点，两点最近的距离。

然后我们进一步发现，把这两个点连起来之后圆心是在这条直线上的。你可以感性思考，这两个点一定都是圆上最凸出来的那个地方，也就是最中间的地方，所以会和圆心位于同一直线。

不懂自己画图玩就会了。

所以这个距离就是，两个圆圆心的距离减去各自半径。

然后题意其实就转化成了最短路，然后就结束了。

一些奇奇怪怪的细节可以自己写，就不说啦。

#include <bits/stdc++.h>
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
constexpr int N = 1005;
int n, to, cnt, head[N], vis[N];
double sx, sy, ex, ey, x[N], y[N], r[N], dis[N];
struct edge {
    int t, nxt;
    double w;
}e[N * N * 2];
inline double Dis(int a, int b) {
    return __builtin_sqrt((x[a] - x[b]) * (x[a] - x[b]) +  (y[a] - y[b]) * (y[a] - y[b]));
}
inline void add(int u, int v, double w) {
    e[++cnt].t = v;
    e[cnt].nxt = head[u];
    e[cnt].w = w;
    head[u] = cnt;
}
void dijkstra() {
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>>q;
    fill(dis, dis + n + 2, 1145141919810);
    dis[0] = 0;
    q.push(make_pair(0, 0));
    while(!q.empty()) {
        auto now = q.top();
        q.pop();
        if(now.first != dis[now.second]) continue;
        for(register int i = head[now.second]; i; i = e[i].nxt) {
            to = e[i].t;
            if(dis[now.second] + e[i].w < dis[to]) {
                dis[to] = dis[now.second] + e[i].w;
                q.push(make_pair(dis[to], to));
            }
        }
    }
}
int main() {
    cin >> sx >> sy >> ex >> ey >> n;
    x[0] = sx, y[0] = sy, x[n + 1] = ex, y[n + 1] = ey;
    rep(i, 1, n) cin >> x[i] >> y[i] >> r[i];
    rep(i, 0, n + 1) {
        rep(j, 0, n + 1) {
            if(i == j) continue;
            add(i, j, max(Dis(i, j) - r[i] - r[j], (double)0));
        }
    }
    dijkstra();
    cout << fixed << setprecision(10) << dis[n + 1];
    return 0;
}