zoj1158判断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) ;
 }
};

int interdiv(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 interdiv(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 lisline ;
vector lispoint ;

int main(){
 int t , k , n , i , j , T = 1 ;
 Point ed , ls , ld ;
 cin>>t ;
 while(t--){
 cin>>n ;
 lispoint.clear() ;
 lisline.clear() ;
 lispoint.push_back(Point(0.0 , 0.0)) ;
 lispoint.push_back(Point(0.0 , 100.0)) ;
 lispoint.push_back(Point(100.0 , 0.0)) ;
 lispoint.push_back(Point(100.0 , 100.0)) ;
 for(i = 1 ; i <= n ; i++){
 ls.read() , ld.read() ;
 lispoint.push_back(ls) ;
 lispoint.push_back(ld) ;
 lisline.push_back(Line(ls , ld)) ;
 }
 ed.read() ;
 int ans = 100000000 , sum ;
 for(i = 0 ; i < lispoint.size() ; i++){
 Line now = Line(lispoint[i] , ed) ;
 sum = 0 ;
 for(j = 0 ; j < lisline.size() ; j++){
 if(now.intersect(lisline[j])) sum++ ;
 }
 ans = min(ans , sum) ;
 }
 if(T != 1) puts("") ;
 T++ ;
 printf("Number of doors = %d\n" , ans+1) ;
 }
 return 0 ;
}