题解：AT_arc064_c [ARC064E] Cosmic Rays

有趣的题目！

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

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

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

不懂自己画图玩就会了。

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

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

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

CPP

#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;
}

题解：AT_arc064_c [ARC064E] Cosmic Rays

文章操作

相关推荐

评论

题解：AT_arc064_c [ARC064E] Cosmic Rays