New Game!
描述
题目描述：
Eagle Jump公司正在开发一款新的游戏。泷本一二三作为其员工，获得了提前试玩的机会。现在她正在试图通过一个迷宫。
这个迷宫有一些特点。为了方便描述，我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线 L1:Ax+By+C1=0, L2:Ax+By+C2=0，
还有 n个圆 Ci:(x−xi)^2+(y−yi)^2=ri^2。角色在直线上、圆上、圆内行走不消耗体力。在其他位置上由S点走到T点消耗的体力为S和T的欧几里得距离。
泷本一二三想从 L1 出发，走到L2 。请计算最少需要多少体力。
输入：
第一行五个正整数 n,A,B,C1,C2 (1≤n≤1000,−10000≤A,B,C1,C2≤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 由于圆是没有消耗的，所以可以将每个圆都坍缩成点，然后求L1到L2的最短路即可。
#include<math.h>
#include<stdio.h>
#define MAXN 1000
struct point
{
double x,y;
};
struct line
{
point a,b;
}; 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[];
double r[];
double e[][],d[];
int used[];
double inf=1e9;
void dij(int s,int n)
{ int v,u,max=; for(u=;u<=n;u++)
d[u]=inf,used[u]=; d[s]=; while()
{ v=-;
for(u=;u<=n;u++)
{ if(!used[u]&&(v==-||d[u]<d[v]))
v=u; }
if(v==-) break;
used[v]=; for(u=;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=;i<=n+;i++)
{
for(int j=;j<=n+;j++)
e[i][j]=inf;
}
for(int i=;i<=n;i++)
{
scanf("%lf%lf%lf",&pp[i].x,&pp[i].y,&r[i]);
} for(int i=;i<=n;i++)
{
double lt=disptoline(pp[i],a,b,c1); if(lt<r[i]) e[][i]=;
else e[][i]=lt-r[i];
}
for(int i=;i<=n;i++)
{
double lt=disptoline(pp[i],a,b,c2);
if(lt<r[i]) e[i][n+]=;
else e[i][n+]=lt-r[i];
}
for(int i=;i<=n;i++)
for(int j=;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]=;
}
point t;
t.y=1.0,t.x=-(b*1.0+c1)/a;
e[][n+]=disptoline(t,a,b,c2);
dij(,n+); printf("%.10f\n",d[n+]);
return ;
}