枚举两点 若不和任何线段相交 建边为dis（i,j) floyd求最短路

1 #include 
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
                10 using namespace std; 11 #define N 100 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 struct point 18 { 19 double x,y; 20 point(double x=0,double y=0):x(x),y(y){} 21 }p[N]; 22 struct line 23 { 24 point u,v; 25 }li[N]; 26 double w[N][N]; 27 typedef point pointt; 28 pointt operator - (point a,point b) 29 { 30 return pointt(a.x-b.x,a.y-b.y); 31 } 32 int dcmp(double x) 33 { 34 if(fabs(x)
               
                o) 96 w[i][j] = w[j][i] = dis(p[i]-p[j]); 97 //printf("%.2f %.2f %.2f %.2f %.2f\n",p[i].x,p[i].y,p[j].x,p[j].y,w[i][j]); 98 } 99 for(i = 1; i <= g+2 ; i++)100 for(j = 1; j <=g+2 ;j++)101 for(k = 1; k <= g+2 ; k++)102 w[j][k] = min(w[j][i]+w[i][k],w[j][k]);103 printf("%.2f\n",w[g+1][g+2]);104 }105 return 0;106 }