本文主要是介绍zoj 1721 判断2条线段（完全）相交，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给出起点，终点，与一些障碍线段。 求起点到终点的最短路。 枚举2点的距离，然后最短路。
2点可达条件：没有线段与这2点所构成的线段（完全）相交。
const double eps = 1e-8 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;
}struct Point{double x , y ;Point(){}Point(double _x , double _y):x(_x),y(_y){}Point operator + (Point o){return Point(add(x , o.x) , add(y , o.y)) ;}Point operator - (Point o){return Point(add(x , -o.x) , add(y , -o.y)) ;}Point operator * (double o){return Point(x*o , y*o) ;}double operator ^(Point o){return add(x*o.y , -y*o.x) ;}double dist(Point o){return sqrt((x-o.x)*(x-o.x) + (y-o.y)*(y-o.y)) ;}void read(){scanf("%lf%lf" ,&x , &y) ;}
};//判断2条线段完全相交
int intersection(Point p1 , Point p2 , Point q1 , Point q2){double d1 = (p2 - p1) ^ (q1 - p1) ;double d2 = (p2 - p1) ^ (q2 - p1) ;double d3 = (q2 - q1) ^ (p1 - q1) ;double d4 = (q2 - q1) ^ (p2 - q1) ;return d1 * d2 < 0 && d3 * d4 < 0 ;
}struct Line{Point s , t ;Line(){}Line(Point _s , Point _t):s(_s),t(_t){}int intersect(Line o){ // 直线与线段O是否相交return intersection(s , t , o.s , o.t) ;}void read(){s.read() , t.read() ;}friend bool operator < (const Line A ,const Line B){return A.s.x < B.s.x ;}
};vector<Line> lisline ;
vector<Point> lispoint ;
double dist[100][100] ;
const double inf = 1000000 ;int ok(Line now){for(int i = 0 ; i < lisline.size() ; i++){if(now.intersect(lisline[i])) return 0 ;}return 1 ;
}void getdist(){int i , j , n = lispoint.size() ;for(i = 0 ; i < n ; i++){dist[i][i] = inf ;for(j = i+1 ; j < n ; j++){if(ok(Line(lispoint[i] , lispoint[j])))dist[i][j] = dist[j][i] = lispoint[i].dist(lispoint[j]) ;else dist[i][j] = dist[j][i] = inf ;}}
}double mindis[100] ;
bool in[100] ;
double spfa(){int i , j , u , v , n = lispoint.size() ;memset(in , 0 , sizeof(in)) ;for(i = 0 ; i < n ; i++) mindis[i] = inf ;queue<int> q ;q.push(0) ;mindis[0] = 0.0 ;in[0] = 1 ;while(! q.empty()){u = q.front() ; q.pop() ;in[u] = 0 ;for(v = 0 ; v < n ; v++){if(dist[u][v] == inf) continue ;if(mindis[u] + dist[u][v] < mindis[v]){mindis[v] = mindis[u] + dist[u][v] ;if(! in[v]){q.push(v) ;in[v] = 1 ;}}}}return mindis[n-1] ;
}int main(){int t , k , n , i , j ;double x , y1 , y2 , y3 , y4 ;while(cin>>n && n!= -1){lisline.clear() ;lispoint.clear() ;lispoint.push_back(Point(0.0 , 5.0)) ;for(i = 1 ; i <= n ; i++){cin>>x>>y1>>y2>>y3>>y4 ;lispoint.push_back(Point(x , y1)) ;lispoint.push_back(Point(x , y2)) ;lispoint.push_back(Point(x , y3)) ;lispoint.push_back(Point(x , y4)) ;lisline.push_back(Line(Point(x , 0) , Point(x , y1))) ;lisline.push_back(Line(Point(x , y2) , Point(x , y3))) ;lisline.push_back(Line(Point(x , y4) , Point(x , 10.0))) ;}lispoint.push_back(Point(10.0 , 5.0)) ;getdist() ;double s = spfa() ;if(s == inf) puts("-1") ;else printf("%.2lf\n" , s) ;}return 0 ;
}
这篇关于zoj 1721 判断2条线段（完全）相交的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
