起点/终点向每个圆的切点连边。
任意两个圆的公切点之间连边。
同一圆上相邻两个关键点之间连边。
然后Dijkstra求最短路即可,时间复杂度$O(n^3)$。
注意判边可行性的时候要忽略这条边来源的圆,可以提高精度。
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
const int N=510,M=1100000;
const double eps=1e-6,PI=acos(-1.0);
inline double sqr(double x){return x*x;}
struct P{
double x,y;
P(){x=y=0;}
P(double _x,double _y){x=_x,y=_y;}
P operator+(const P&v)const{return P(x+v.x,y+v.y);}
P operator-(const P&v)const{return P(x-v.x,y-v.y);}
P operator*(double v)const{return P(x*v,y*v);}
P operator/(double v)const{return P(x/v,y/v);}
double operator*(const P&v){return x*v.x+y*v.y;}
double len(){return hypot(x,y);}
double len_sqr(){return x*x+y*y;}
P rotate(double c)const{return P(x*cos(c)-y*sin(c),x*sin(c)+y*cos(c));}
P trunc(double l){return(*this)*l/len();}
void read(){scanf("%lf%lf",&x,&y);}
}a[M];
int n,cnt,i,j,cp[N],pool[N][2205];double w[M];
inline bool cmp(int x,int y){return w[x]<w[y];}
inline double cross(const P&a,const P&b){return a.x*b.y-a.y*b.x;}
struct Cir{
P c;double r,rr;
void read(){c.read();scanf("%lf",&r);rr=sqr(r);}
P point(double a)const{return P(c.x+r*cos(a),c.y+r*sin(a));}
bool intersection(const P&a,const P&b){
if((c-a)*(b-a)>-eps&&(c-b)*(a-b)>-eps)return sqr(cross(c-a,b-a))-rr*(b-a).len_sqr()<-eps;
if((c-a).len_sqr()-rr<-eps)return 1;
return (c-b).len_sqr()-rr<-eps;
}
}b[N];
namespace G{
const int MAXE=M*3;
int g[M],v[MAXE],nxt[MAXE],ed;double w[MAXE],d[M];
typedef pair<double,int>P;
priority_queue<P,vector<P>,greater<P> >q;
inline void add(int x,int y,double z){v[++ed]=y;w[ed]=z;nxt[ed]=g[x];g[x]=ed;}
inline void ext(int x,double y){if(y+eps<d[x])q.push(P(d[x]=y,x));}
double solve(){
for(i=1;i<=cnt;i++)d[i]=1e9;
ext(1,0);
while(!q.empty()){
P t=q.top();q.pop();
if(d[t.second]+eps<t.first)continue;
for(i=g[t.second];i;i=nxt[i])ext(v[i],t.first+w[i]);
}
return d[2];
}
}
inline void add(int x,int y,int z,int u=0,int v=0){
for(int i=1;i<=n;i++)if(i!=u&&i!=v)if(b[i].intersection(a[x],a[y]))return;
double t=(a[x]-a[y]).len();
G::add(x,y,t);
if(z==2)G::add(y,x,t);
}
inline void getTangents(const P&p,const Cir&C,int v){
P u=C.c-p;
double dist=u.len(),ang=asin(C.r/dist);
u=u.trunc(sqrt(u.len_sqr()-sqr(C.r)));
a[++cnt]=u.rotate(-ang)+p;
pool[v][++cp[v]]=cnt;
a[++cnt]=u.rotate(ang)+p;
pool[v][++cp[v]]=cnt;
}
inline void getTangents(Cir A,Cir B,int u,int v){
if(A.r<B.r)swap(A,B),swap(u,v);
double d=(A.c-B.c).len();
double base=atan2(B.c.y-A.c.y,B.c.x-A.c.x);
double ang=acos((A.r-B.r)/d); a[++cnt]=A.point(base+ang);
pool[u][++cp[u]]=cnt;
a[++cnt]=B.point(base+ang);
pool[v][++cp[v]]=cnt;
add(cnt-1,cnt,2,u,v); a[++cnt]=A.point(base-ang);
pool[u][++cp[u]]=cnt;
a[++cnt]=B.point(base-ang);
pool[v][++cp[v]]=cnt;
add(cnt-1,cnt,2,u,v); ang=acos((A.r+B.r)/d); a[++cnt]=A.point(base+ang);
pool[u][++cp[u]]=cnt;
a[++cnt]=B.point(PI+base+ang);
pool[v][++cp[v]]=cnt;
add(cnt-1,cnt,2,u,v); a[++cnt]=A.point(base-ang);
pool[u][++cp[u]]=cnt;
a[++cnt]=B.point(PI+base-ang);
pool[v][++cp[v]]=cnt;
add(cnt-1,cnt,2,u,v);
}
inline void solve(int n,int*q,const Cir&C){
if(n<2)return;
int i;
for(i=1;i<=n;i++)w[q[i]]=atan2(a[q[i]].y-C.c.y,a[q[i]].x-C.c.x);
sort(q+1,q+n+1,cmp);
q[n+1]=q[1];
for(i=1;i<=n;i++){
double t=fabs(w[q[i]]-w[q[i+1]]);
t=min(t,PI*2-t)*C.r;
G::add(q[i],q[i+1],t);
G::add(q[i+1],q[i],t);
}
}
int main(){
cnt=2;
a[1].read();
a[2].read();
scanf("%d",&n);
for(i=1;i<=n;i++)b[i].read();
add(1,2,1);
for(i=1;i<=n;i++){
getTangents(a[1],b[i],i);
add(1,cnt-1,1,i);
add(1,cnt,1,i);
getTangents(a[2],b[i],i);
add(cnt-1,2,1,i);
add(cnt,2,1,i);
}
for(i=1;i<=n;i++)for(j=1;j<i;j++)getTangents(b[i],b[j],i,j);
for(i=1;i<=n;i++)solve(cp[i],pool[i],b[i]);
return printf("%.1f",G::solve()),0;
}