起点/终点向每个圆的切点连边。

任意两个圆的公切点之间连边。

同一圆上相邻两个关键点之间连边。

然后Dijkstra求最短路即可，时间复杂度$O(n^3)$。

注意判边可行性的时候要忽略这条边来源的圆，可以提高精度。

 

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          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]
          
           -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
           
            P;priority_queue
            
             
,greater
             
 >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