我水爆了- -

　　容易发现可以把两个圆之间连边，左上为起点右下为终点，最小生成树直到起点跟终点连起来，输出边权/2就行。

　　然后80.

　　并不理解为什么这可以转化成spfa求最短路，邻接矩阵暴力跑一下就AC了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define maxn 3030using namespace std;inline long long read(){ long long num=0,f=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-') f=-1; ch=getchar(); } while(isdigit(ch)){ num=num*10+ch-'0'; ch=getchar(); } return num*f;}struct Node{ double x,y; };inline double calc(Node a,Node b){ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }Node q[maxn];struct Edge{ int from,to; double val; bool operator <(const Edge a)const{ return val
            

f; f.push(up); f.push(left); for(int i=1;i<=right;++i) dis[i]=0x7ffffffff; dis[up]=dis[left]=0; while(!f.empty()){ int from=f.front();f.pop(); vis[from]=0; for(int to=1;to<=right;++to){ if(max(mp[from][to],dis[from])