New Game!
题目描述
Eagle Jump公司正在开发一款新的游戏。Hifumi Takimoto作为其中的员工，获得了提前试玩的机会。现在她正在试图通过一个迷宫。
这个迷宫有一些特点。为了方便描述，我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线$ L_1:Ax+By+C1=0, L_2:Ax+By+C2=0$，还有 n 个圆 $C_i:(x-x_i)^2 + (y - y_i)^2 = r_i^2$。角色在直线上、圆上、圆内行走不消耗体力。在其他位置上由S点走到T点消耗的体力为S和T的欧几里得距离。
Hifumi Takimoto想从 $L_1$ 出发，走到 $L_2$ 。请计算最少需要多少体力。
输入描述
第一行五个正整数 $n,A,B,C_1,C_2$ ($1≤ n ≤ 1000, -10000 ≤ A,B,C_1,C_2 ≤ 10000$)，其中 A,B 不同时为 0。
接下来 n 行每行三个整数 $x,y,r(-10000 ≤ x,y ≤ 10000, 1≤ r ≤ 10000) $表示一个圆心为 $(x,y)$，半径为 $r$的圆。
输出描述
仅一行一个实数表示答案。与正确结果的绝对误差或者相对误差不超过 $10^{-4}$ 即算正确。
输入
2 0 1 0 -4
0 1 1
1 3 1输出
0.236068链接
https://www.nowcoder.com/acm/contest/201/L
题意
如题，问从直线$L_1$到$L_2$的最短距离。
题解
题目关键在角色在直线上、圆上、圆内行走不消耗体力，所以可以把直线和圆都看成一个点，然后建图，直线$L_1$为起点，直线 $L_2$为终点，跑最短路径即可。
代码
- 答案正确 76ms 32608KB 2604
#include <bits/stdc++.h>
using namespace std;
const double inf = 1e9;
const double eps = 1e-9;
const int maxn = 1010;
int N, n;
double A, B, C1, C2;
double dist[maxn];
bool vis[maxn];
struct Node
{
int v;
double c;
Node (int _v, double _c): v(_v), c(_c) {}
bool operator < (const Node & r) const
{
return c > r.c;
}
};
struct Edge
{
int to;
double cost;
Edge(int _to, double _cost): to(_to), cost(_cost) {}
};
vector <Edge> edge[maxn];
void addedge(int u, int v, double w)
{
edge[u].push_back(Edge(v, w));
}
struct Circle
{
double x, y, r;
}circle[maxn];
double dist1(Circle a, Circle b) // 两个“圆”的距离
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)) - a.r - b.r;
}
double dist2(double C, Circle d) // “圆”到直线的距离
{
return (fabs(A * d.x + B * d.y + C) / sqrt(A * A + B * B) - d.r);
}
double dijkstra(int s, int t) // 最短路
{
for (int i = 0; i <= N; ++i)
{
dist[i] = inf;
vis[i] = false;
}
dist[s] = 0;
priority_queue <Node> Q;
Q.push(Node(s, dist[s]));
while (!Q.empty())
{
Node tmp = Q.top();
Q.pop();
int u = tmp.v;
if (u == t) // 到达t即返回
return tmp.c;
if (vis[u])
continue;
vis[u] = true;
for (int i = 0; i < edge[u].size(); ++i)
{
int v = edge[u][i].to;
double cost = edge[u][i].cost;
if (!vis[v] && dist[v] > dist[u] + cost)
{
dist[v] = dist[u] + cost;
Q.push(Node(v, dist[v]));
}
}
}
return 0;
}
int main()
{
scanf("%d%lf%lf%lf%lf", &n, &A, &B, &C1, &C2);
for (int i = 1; i <= n; ++i)
scanf("%lf%lf%lf", &circle[i].x, &circle[i].y, &circle[i].r);
N = n + 1; // 总点数
for (int i = 1; i <= n; ++i) // 起点与圆
{
double w = dist2(C1, circle[i]);
if (w > eps)
addedge(0, i, w);
else
addedge(0, i, 0);
}
for (int i = 1; i <= n; ++i) // 圆与终点
{
double w = dist2(C2, circle[i]);
if (w > eps)
addedge(i, N, w);
else
addedge(i, N, 0);
}
for (int i = 1; i <= n; ++i) // 圆间
{
for (int j = 1; j <= n; ++j)
{
double w = dist1(circle[i], circle[j]);
if (w > eps)
{
addedge(i, j, w);
addedge(j, i, w);
}
else
{
addedge(i, j, 0);
addedge(j, i, 0);
}
}
}
double ans = dijkstra(0, N);
printf("%.7f\n", ans);
return 0;
}The end.
2018-10-24 星期三