zoj 1158 判断2线段完全相交

一个正方形的古老墓园，有n面墙，墙的端点都在正方形的边上。已知墓碑的地点(x,y)，问从外面一直到达墓碑至少要凿开几个门，而且规定门只能凿在当前点段的中点。 思路很巧妙，因为从一个点到终点不可能“绕过”围墙，只能传过去，所以门是否开在中点是无所谓

一个正方形的古老墓园，有n面墙，墙的端点都在正方形的边上。已知墓碑的地点(x,y)，问从外面一直到达墓碑至少要凿开几个门，而且规定门只能凿在当前点段的中点。

思路很巧妙，因为从一个点到终点不可能“绕过”围墙，只能传过去，所以门是否开在中点是无所谓的，只要求四周线段中点到终点的线段与墙的最少交点个数即可。更进一步，实际上，只需判断四周围墙的所有点与终点的连线与内墙的最少交点加一即可。

Pix2Pix

使用Prompt编辑视频

下载

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<Line> lisline  ;
vector<Point> 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 ;
}