New Game! 描述 题目描述: Eagle Jump公司正在开发一款新的游戏。泷本一二三作为其员工,获得了提前试玩的机会。现在她正在试图通过一个迷宫。
这个迷宫有一些特点。为了方便描述,我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线L1:Ax+By+C1=0,L2:Ax+By+C2=0L1:Ax+By+C1=0,L2:Ax+By+C2=0 L_1:Ax+By+C_1=0, L_2:Ax+By+C_2=0,还有 n个圆Ci:(x−xi)2+(y−yi)2=ri2n个圆Ci:(x−xi)2+(y−yi)2=ri2n 个圆 C_i:(x-x_i)^2+(y-y_i)^2={r_i}^2。角色在直线上、圆上、圆内行走不消耗体力。在其他位置上由S点走到T点消耗的体力为S和T的欧几里得距离。
泷本一二三想从L1L1 L_1 出发,走到 L2L2L_2 。请计算最少需要多少体力。
输入: 第一行五个正整数 n,A,B,C1,C2(1≤n≤1000,−10000≤A,B,C1,C2≤10000)n,A,B,C1,C2(1≤n≤1000,−10000≤A,B,C1,C2≤10000)n,A,B,C_1,C_2 (1\le n \le 1000, -10000 \le A,B,C_1,C_2 \le 10000),其中 A,B 不同时为 0。
接下来 n 行每行三个整数 x,y,r(−10000≤x,y≤10000,1≤r≤10000)x,y,r(−10000≤x,y≤10000,1≤r≤10000)x,y,r(-10000 \le x,y \le 10000, 1\le r \le 10000)表示一个圆心为 (x,y),半径为 r 的圆。
输出: 仅一行一个实数表示答案。与标准答案的绝对误差或者相对误差不超过10−410−4 10^{-4} 即算正确。
样例输入 2 0 1 0 -4 0 1 1 1 3 1 样例输出 0.236068
由于圆是没有消耗的,所以可以将每个圆都坍缩成点,然后求L1到L2的最短路即可。
#include<iostream>
#include<cmath>
#include<cstdio>
#define MAXN 1005
using namespace std;
struct point
{
double x, y;
point() {
}
};
struct line
{
point a, b;
line() {
}
};
double distance(point p1, point p2)
{
return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
double disptoline(point p1, double a, double b, double c)
{
double x = sqrt(a*a + b*b);
return fabs((a*p1.x + b*p1.y + c) / x);
}
point pp[1005];
double r[1005];
double e[1005][1005], d[1005];
int used[1005];
double inf = 1e9;
void dij(int s, int n)
{
int v, u, max = 0;
for (u = 0; u <= n; u++)
d[u] = inf, used[u] = 0;
d[s] = 0;
while (1)
{
v = -1;
for (u = 0; u <= n; u++)
{
if (!used[u] && (v == -1 || d[u]<d[v]))
v = u;
}
if (v == -1) break;
used[v] = 1;
for (u = 0; u <= n; u++)
if (d[u]>d[v] + e[v][u])
d[u] = d[v] + e[v][u];
}
}
int main()
{
int n;
double a, b, c1, c2;
scanf("%d", &n);
scanf("%lf%lf%lf%lf", &a, &b, &c1, &c2);
for (int i = 0; i <= n + 1; i++)
{
for (int j = 0; j <= n + 1; j++)
e[i][j] = inf;
}
for (int i = 1; i <= n; i++)
{
scanf("%lf%lf%lf", &pp[i].x, &pp[i].y, &r[i]);
}
for (int i = 1; i <= n; i++)
{
double lt = disptoline(pp[i], a, b, c1);
if (lt<r[i]) e[0][i] = 0;
else e[0][i] = lt - r[i];
}
for (int i = 1; i <= n; i++)
{
double lt = disptoline(pp[i], a, b, c2);
if (lt<r[i]) e[i][n + 1] = 0;
else e[i][n + 1] = lt - r[i];
}
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
if (i == j) continue;
double lt = distance(pp[i], pp[j]);
if (lt>r[i] + r[j]) e[i][j] = lt - r[i] - r[j];
else e[i][j] = 0;
}
point t;
t.y = 1.0, t.x = -(b*1.0 + c1) / a;
e[0][n + 1] = disptoline(t, a, b, c2);
dij(0, n + 1);
printf("%.6f\n", d[n + 1]);
return 0;
}