Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内-mysql教程-PHP中文网

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

php中文网

发布： 2016-06-07 15:49:52

原创

1172人浏览过

题目点击打开链接凸多边形A，多边形B，判断B是否严在A内。注意AB有重点。将A,B上的点合在一起求凸包，如果凸包上的点是B的某个点，则B肯定不在A内。或者说B上的某点在凸包的边上则也说明B不严在A里面。这个处理有个巧妙的方法，只需在求凸包的时候，

题目点击打开链接

凸多边形A，多边形B，判断B是否严格在A内。

注意AB有重点。

将A,B上的点合在一起求凸包，如果凸包上的点是B的某个点，则B肯定不在A内。

或者说B上的某点在凸包的边上则也说明B不严格在A里面。

讯飞开放平台

科大讯飞推出的以语音交互技术为核心的AI开放平台

152

查看详情

这个处理有个巧妙的方法，只需在求凸包的时候，

另外不能去重点。

int   cmp(double x){
      if(fabs(x) < 1e-8)  return 0 ;
      return  x > 0 ? 1 : -1 ;
}

struct  point{
        double x , y ;
        int k ;
        point(){}
        point(double _x , double _y):x(_x) , y(_y){}
        point operator - (const point &o){
              return  point(x - o.x , y - o.y) ;
        }
        friend double operator ^ (const point &a , const point &b){
              return a.x * b.y - a.y * b.x ;
        }
        friend bool operator < (const point &a , const point &b){
              if(cmp(a.x - b.x) != 0)  return cmp(a.x - b.x) < 0 ;
              if(cmp(a.y - b.y) != 0)  return  cmp(a.y - b.y) < 0 ;
              return  a.k < b.k ;
        }
        friend bool operator == (const point &a , const point &b){
             return cmp(a.x - b.x) == 0 && cmp(a.y - b.y) == 0 ;
        }
};

vector<point>  convex_hull(vector<point> a){
       vector<point>  s(a.size() * 2 + 5) ;
       sort(a.begin() , a.end()) ;
       int m = 0  ;
       for(int i = 0 ; i < a.size() ; i++){
            while(m > 1 && cmp((s[m-1] - s[m-2]) ^ (a[i] - s[m-2])) < 0) m-- ;
            s[m++] = a[i] ;
       }
       int k = m ;
       for(int i = a.size() - 2 ; i >= 0 ; i--){
            while(m > k && cmp((s[m-1] - s[m-2]) ^ (a[i] - s[m-2])) < 0) m-- ;
            s[m++] = a[i] ;
       }
       s.resize(m) ;
       if(a.size() > 1) s.resize(m-1) ;
       return s ;
}

int   main(){
      int i , n ,  m  , ans = 0  ;
      vector<point> lis(200000) ;
      cin>>n;
      for(i = 0 ; i < n ; i++){
          scanf("%lf%lf" , &lis[i].x , &lis[i].y) ;
          lis[i].k = 0 ;
      }
      cin>>m ;
      for(i = 0 ; i < m ; i++){
          scanf("%lf%lf" , &lis[n+i].x , &lis[n+i].y) ;
          lis[n+i].k = 1 ;
      }
      lis.resize(n + m)  ;
      vector<point> hull = convex_hull(lis)  ;
      for(i = 0 ; i < hull.size() ; i++){
          if(hull[i].k){
               ans = 1 ;
               break  ;
          }
      }
      printf("%s\n" , ans ? "NO" : "YES") ;
      return  0 ;
}

登录后复制