易知最短路一定是以圆心或者两圆交点作为中间点到达的。所以把这些点拿出来建图跑最短路就够了。
如今的问题就是，给定两个点，是否能连边 add(a,b,dist(a,b))
题目要求，ab线段必须全然在圆上，所以能够求出ab线段和全部圆的全部交点，对于随意相邻两个交点，它们必处于同一个圆内，否则不可达。点的编号用map就够了（一開始我以为double有精度问题无法map。用两个longlong保存然后乘上1000000000，后来发现没问题。应该是这题都是整点，精度要求不高的原因吧）
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
#include <cstring>
using namespace std;
#define pi acos(-1.0)
#define eps 1e-10
int cmp(double x)
{
if(fabs(x)<eps) return 0;
if(x>0) return 1;
return -1;
}
double sqr(double x)
{
return x*x;
}
struct point
{
double x,y;
point(){};
point(double a,double b):x(a),y(b){};
void out()
{
printf("%lf %lf
",x,y);
}
void input()
{
scanf("%lf%lf",&x,&y);
}
friend point operator +(const point &a,const point &b)
{
return point(a.x+b.x,a.y+b.y);
}
friend point operator -(const point &a,const point &b)
{
return point(a.x-b.x,a.y-b.y);
}
friend bool operator ==(const point &a,const point &b)
{
return cmp(a.x-b.x)==0&&cmp(a.y-b.y)==0;
}
bool operator <(const point &a) const
{
if(x==a.x) return y<a.y;
return x<a.x;
}
friend point operator *(const point &a,const double &b)
{
return point(a.x*b,a.y*b);
}
friend point operator *(const double &a,const point &b)
{
return point(a*b.x,a*b.y);
}
friend point operator /(const point &a,const double &b)
{
return point(a.x/b,a.y/b);
}
double norm()
{
return sqrt(sqr(x)+sqr(y));
}
};
double det(const point &a,const point &b)
{
return a.x*b.y-a.y*b.x;
}
double dot(const point&a,const point &b)
{
return a.x*b.x+a.y*b.y;
}
double dist(const point &a,const point &b)
{
return (a-b).norm();
}
point rotate_point(const point &p,double A)
{
double tx=p.x,ty=p.y;
return point(tx*cos(A)-ty*sin(A),tx*sin(A)+ty*cos(A));
}
point rotate(const point &p,double cost,double sint)
{
double x=p.x,y=p.y;
return point(x*cost-y*sint,x*sint+y*cost);
}
pair<point,point> crosspoint(point ap,double ar,point bp,double br)
{
double d=(ap-bp).norm();
double cost = (ar*ar + d*d -br*br)/(2*ar*d);
double sint=sqrt(1.0-cost*cost);
point v=(bp-ap)/(bp-ap).norm()*ar;
return make_pair(ap+rotate(v,cost,-sint),ap+rotate(v,cost,sint));
}
void circle_cross_line(point a,point b,point o,double r,point ret[],int &num) {
double x0 = o.x ,y0 = o.y;
double x1 = a.x, y1 = a.y;
double x2 = b.x, y2 = b.y;
double dx = x2-x1, dy = y2-y1;
double A = dx*dx+dy*dy;
double B = 2*dx*(x1-x0) + 2*dy*(y1-y0);
double C = sqr(x1-x0) + sqr(y1-y0)-sqr(r);
double delta = B*B-4*A*C;
if( cmp(delta) >= 0) {
double t1 = (-B - sqrt(delta)) / (2*A);
double t2 = (-B + sqrt(delta)) / (2*A);
if(cmp(t1-1)<=0 && cmp(t1)>=0)
ret[num++] = point(x1+t1*dx,y1+t1*dy);
if(cmp(t2-1) <=0 && cmp(t2)>=0)
ret[num++] = point(x1+t2*dx,y1+t2*dy);
}
}
struct rad
{
point c;
double r;
}ra[300];
int n;
map<point,int> mp;
int ID;
int que[123456];
point xx[100005];
struct node2
{
int v,next;
double w;
}e[123456];
int head[12345];
bool in[12345];
double d[12345];
int en;
void add(int a,int b,double c)
{
// printf("%d %d %lf
",a,b,c);
e[en].v=b;
e[en].w=c;
e[en].next=head[a];
head[a]=en++;
e[en].v=a;
e[en].w=c;
e[en].next=head[b];
head[b]=en++;
}
void spfa(int st)
{
queue<int> q;
memset(in,0,sizeof(in));
for(int i=1;i<=ID;i++) d[i]=1000000000;
q.push(st);
in[st]=1;
d[st]=0;
int tmp;
while(!q.empty())
{
tmp=q.front();q.pop();
in[tmp]=0;
for(int i=head[tmp];~i;i=e[i].next)
{
if(d[e[i].v]>d[tmp]+e[i].w)
{
d[e[i].v]=d[tmp]+e[i].w;
if(!in[e[i].v])
{
in[e[i].v]=1;
q.push(e[i].v);
}
}
}
}
}
bool inra(point &x,point &y)
{
for(int i=1;i<=n;i++)
{
if(dist(x,ra[i].c)<=ra[i].r+eps && dist(y,ra[i].c)<=ra[i].r+eps)
{
return true;
}
}
return false;
}
point my[12345];
bool cal(point &a,point &b)
{
my[0]=a;
int top=1;
for(int i=1;i<=n;i++)
{
circle_cross_line(a,b,ra[i].c,ra[i].r,my,top);
}
my[top++]=b;
sort(my,my+top);
for(int i=1;i<top;i++)
{
if(!inra(my[i-1],my[i])) return false;
}
return true;
}
int main()
{
int ca=1;
int cas;
scanf("%d",&cas);
while(cas--)
{
mp.clear();
scanf("%d",&n);
ID=0;
for(int i=1;i<=n;i++)
{
ra[i].c.input();
scanf("%lf",&ra[i].r);
}
printf("Case %d: ",ca++);
if(cal(ra[1].c,ra[n].c)) //冲榜都靠这个特判#_#
{
printf("%.4f
",dist(ra[1].c,ra[n].c));
continue;
}
en=0;
memset(head,-1,sizeof(head));
int top=0;
for(int i=1;i<=n;i++)
{
mp[ra[i].c]=++ID;
que[top++]=ID;
xx[ID]=ra[i].c;
for(int j=i+1;j<=n;j++)
{
if(dist(ra[i].c,ra[j].c)>(ra[i].r+ra[j].r)+0.0) continue;
pair<point,point> tmp=crosspoint(ra[i].c,ra[i].r,ra[j].c,ra[j].r);
if(mp[tmp.first]==0)
{
mp[tmp.first]=++ID;
que[top++]=ID;
xx[ID]=tmp.first;
}
if(mp[tmp.second]==0)
{
mp[tmp.second]=++ID;
que[top++]=ID;
xx[ID]=tmp.second;
}
}
}
mp[ra[n].c]=++ID;
que[top++]=ID;
xx[ID]=ra[n].c;
for(int i=0;i<top;i++)
{
for(int j=i+1;j<top;j++)
{
if(cal(xx[que[i]],xx[que[j]]))
{
add(que[i],que[j],dist(xx[que[i]],xx[que[j]]));
}
}
}
spfa(1);
if(d[ID]>=1000000000) puts("No such path.");
else printf("%.4f
",d[ID]);
}
return 0;
}
/*
99
2
0 0 1
2 0 1
2
0 0 1
4 1 2
4
-4 0 1
-1 0 2
1 0 2
4 0 1
3
-3 0 1
0 0 2
0 3 1
3
-3 0 1
0 0 2
-2 -1 1
3
-3 0 1
-2 -1 1
0 0 2
4
2 2 2
2 -2 2
-2 2 2
-2 -2 2
2
0 0 3
1 0 1
3
0 0 1
2 2 2
3 0 1
3
0 0 1
3 0 1
2 2 2
ans:
2.0000
No
8.0000
4.8284
1.4142
3.0000
6.8284
1.0000
3.0654
2.8284
*/