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 ;
}