画几个图后，知道路径点集一定是起点终点加上圆与圆之间的交点，枚举每两个点之间是否能走，能走则连上线，然后求一遍最短路即可
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define sqr(x) ((x)*(x))
const double eps= 1e-;
const int maxc=;
const int maxp=;
const double inf=1e20;
double dsgn(double x)//return double
{
if(fabs(x)<eps)return ;
return x;
}
int isgn(double x)//return int
{
if(fabs(x)<eps)return ;
if(x<)return -;
return ;
}
struct point
{
double x, y;
point() {}
point(double xx, double yy):x(xx), y(yy) {}
double length() const
{
return sqrt(sqr(x)+sqr(y));
}
point set(const double &m) const
{
double len=length();
return point(x*m/len, y*m/len);
}
double sqrdist(const point &a)const
{
return sqr(a.x-x)+sqr(a.y-y);
}
double dist(const point &a)const
{
return sqrt(sqrdist(a));
}
} p[maxp];
struct line
{
double a, b, c;
line() {}
line(double ta=, double tb=-, double tc=):a(ta), b(tb), c(tc) {}
};
struct circle
{
point o;
double r;
} c[maxc];
int pn, cn;
double edge[maxp][maxp]; int cir_relation(circle c1, circle c2)//判断两圆关系
{
double d=c1.o.dist(c2.o);
int a=isgn(d-c1.r-c2.r);
int b=isgn(d-fabs(c1.r-c2.r));
if(a==)return -;//外切
if(b==)return -;//内切
if(a>)return ;//相离
if(b<)return ;//内含
return ;//相交
}
point line_intersect(point p1, point p2, point q1, point q2)
{
point ans=p1;
double t=((p1.x-q1.x)*(q1.y-q2.y)-(p1.y-q1.y)*(q1.x-q2.x))/
((p1.x-p2.x)*(q1.y-q2.y)-(p1.y-p2.y)*(q1.x-q2.x));
ans.x += (p2.x-p1.x)*t;
ans.y += (p2.y-p1.y)*t;
return ans;
}
void line_cross_circle(point p, point q, point o, double r, point &pp, point &qq)
{
point tmp=o;
tmp.x += p.y-q.y;
tmp.y += q.x-p.x;
tmp=line_intersect(tmp, o, p, q);
double t=sqrt(r*r - sqr(tmp.dist(o)))/(p.dist(q));
pp.x=tmp.x + (q.x-p.x)*t;
pp.y=tmp.y + (q.y-p.y)*t;
qq.x=tmp.x - (q.x-p.x)*t;
qq.y=tmp.y - (q.y-p.y)*t;
}
void circle_intersect(circle c1, circle c2, point &p1, point &p2)
{
point u, v;
double t, d;
d=c1.o.dist(c2.o);
t= (+ (sqr(c1.r) -sqr(c2.r))/sqr(d))/;
u.x= c1.o.x+ (c2.o.x-c1.o.x)*t;
u.y= c1.o.y+ (c2.o.y-c1.o.y)*t;
v.x= u.x+c1.o.y-c2.o.y;
v.y= u.y-c1.o.x+c2.o.x;
line_cross_circle(u, v, c1.o, c1.r, p1, p2);
}
point circle_tangent(circle c1, circle c2)
{
point t;
if(isgn(c1.o.dist(c2.o)-c1.r-c2.r)==)
{
t.x=(c1.r*c2.o.x + c2.r*c1.o.x)/(c1.r+c2.r);
t.y=(c1.r*c2.o.y + c2.r*c1.o.y)/(c1.r+c2.r);
return t;
}
t.x=(c1.r*c2.o.x-c2.r*c1.o.x)/(c1.r-c2.r);
t.y=(c1.r*c2.o.y-c2.r*c1.o.y)/(c1.r-c2.r);
return t;
}
void findallpoint()
{
int i, j, rel;
point p1, p2;
for(i=; i<=cn; i++)
for(j=i+; j<=cn; j++)
{
rel=cir_relation(c[i], c[j]);
if(rel==)
{
circle_intersect(c[i], c[j], p1, p2);
p[pn++]=p1;
p[pn++]=p2;
}
else if(rel<)
p[pn++]=circle_tangent(c[i], c[j]);
}
} point tmp[];
point qq[], base;
bool cmp(point a, point b)
{
return a.dist(base)<b.dist(base);
}
bool insideok(point a, point b)
{
for(int i=; i<=cn; i++)
{
if(isgn(c[i].r-a.dist(c[i].o))<)continue;
if(isgn(c[i].r-b.dist(c[i].o))<)continue;
return true;
}
return false;
}
double multiply(point sp, point ep, point op)
{
return (sp.x-op.x)*(ep.y-op.y)-(sp.y-op.y)*(ep.x-op.x);
}
bool onsegment(point a, point u, point v)
{
return isgn(multiply(v, a, u))== && isgn((u.x-a.x)*(v.x-a.x))<= && isgn((u.y-a.y)*(v.y-a.y))<=;
} bool edgeok(point a, point b)
{
int i, j;
int cnt=, num; tmp[cnt++]=a;
point p1, p2;
for(i=; i<=cn; i++)
{
line_cross_circle(a, b, c[i].o, c[i].r, p1, p2);
if(onsegment(p1, a, b))tmp[cnt++]=p1;
if(onsegment(p2, a, b))tmp[cnt++]=p2;
}
tmp[cnt++]=b; base=a;
sort(tmp, tmp+cnt, cmp);
for(i=; i<cnt; i++)
if(!insideok(tmp[i-], tmp[i]))
return false;
return true;
}
void findalledge()
{
int i, j;
for(i=; i<pn; i++)
for(j=i+; j<pn; j++)
{
if(edgeok(p[i], p[j]))
edge[i][j]=edge[j][i]=p[i].dist(p[j]);
else
edge[i][j]=edge[j][i]=-;
}
}
bool has[maxp];
double dis[maxp];
void dijkstra()
{
int i, j, num;
double tmp;
for(i=; i<pn; i++)has[i]=false, dis[i]=inf;
dis[]=;
for(i=; i<pn; i++)
{
tmp=inf;
for(j=; j<pn; j++)
if(!has[j] && dis[j]<tmp)
{
tmp=dis[j];
num=j;
}
has[num]=true;
for(j=; j<pn; j++)
if(!has[j] && isgn(edge[num][j])>=)
dis[j]=min(dis[j], dis[num]+edge[num][j]);
}
if(dis[]<inf)printf("%.4lf\n", dis[]);
else printf("No such path.\n");
} void solve()
{
findallpoint();
findalledge();
dijkstra();
} int main()
{
int t, ca=;
scanf("%d", &t);
while(t--)
{
scanf("%d", &cn);
for(int i=; i<=cn; i++)
scanf("%lf%lf%lf", &c[i].o.x, &c[i].o.y, &c[i].r);
pn=;
p[pn++]=c[].o;
p[pn++]=c[cn].o;
printf("Case %d: ", ca++);
solve();
}
return ;
}