SGU 253 计算几何判定点是否在凸包内-白红宇

SGU 253 计算几何判定点是否在凸包内

阅读量：2439 次

发布时间：2019-05-10

本文共 3002 字，大约阅读时间需要 10 分钟。

/*******************************************************************************   心血来潮上SGU敲了道计算几何～SGU的数据一如既往的BT啊！题意就是给定一个凸包，然后再给定若干个点，询问是否有至少K个点在凸包内，因为数据规模比较大，O(n)的判定算法必然超时，AC核武的博客上有篇讲O(log n)的判定算法的博客，就是极角排序+二分，相当犀利～*******************************************************************************/#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #include 
                      
                       #include 
                       
                        #include 
                        
                         #include 
                         #include 
                          
                           using namespace std;#define LOWBIT(x) ( (x) & ( (x) ^ ( (x) - 1 ) ) )#define CLR(x, k) memset((x), (k), sizeof(x))#define CPY(t, s) memcpy((t), (s), sizeof(s))#define SC(t, s) static_cast
                           
                            (s)#define LEN(s) static_cast
                            
                             ( strlen((s)) )#define SZ(s) static_cast
                             
                              ( (s).size() )typedef double LF;typedef __int64 LL; //VCtypedef unsigned __int64 ULL;typedef pair
                              
                                PII;typedef pair
                               
                                 PLL;typedef pair
                                
                                  PDD;typedef vector
                                 
                                   VI;typedef vector
                                  
                                    VC;typedef vector
                                   
                                     VF;typedef vector
                                    
                                      VS;template 
                                     
                                      T sqa(const T & x){ return x * x;}template 
                                      
                                       T gcd(T a, T b){ if (!a || !b) { return max(a, b); } T t; while (t = a % b) { a = b; b = t; } return b;};const int INF_INT = 0x3f3f3f3f;const LL INF_LL = 0x7fffffffffffffffLL; //15fconst double oo = 10e9;const double eps = 10e-7;const double PI = acos(-1.0);#define ONLINE_JUDGEconst int MAXN = 100004;int n, m, k;struct Point{ int x, y;}pnt[MAXN];struct Segment{ int vx, vy; Segment() {} Segment(Point po, Point pt) { vx = pt.x - po.x; vy = pt.y - po.y; } LL operator * (const Segment & rhs) const { return LL(vx) * LL(rhs.vx) + LL(vy) * LL(rhs.vy); } LL operator ^ (const Segment & rhs) const { return LL(vx) * LL(rhs.vy) - LL(vy) * LL(rhs.vx); }};bool cmpXY(const Point & lhs, const Point & rhs){ return lhs.y != rhs.y ? lhs.y < rhs.y : lhs.x < rhs.x;}bool cmpPK(const Point & lhs, const Point & rhs){ return (Segment(pnt[0], lhs) ^ Segment(pnt[0], rhs)) > 0; //逆时针的极角排序，>改
                                       <就是顺时针的了}bool inpolygon(const point & pt){ int low="1," high="n" - 2, mid="(low" + high) res="-1;" bool sign="true;" token; ll flag[2]; while (low < { 2; flag[0]="(Segment(pnt[0]," pt) ^ segment(pnt[0], pnt[mid])); if (0="=" flag[0]) token="mid" break ; } flag[1] pnt[mid 1])); flag[1]) 1; (flag[0] * 0) nx的数据点，在这wa了两次 0 &&>
                                         0 || flag[0] > 0 && flag[1] < 0) { res = mid; break ; } if (flag[0] < 0 && flag[1] < 0) { low = mid + 1; } else { high = mid - 1; } } if (sign) { if ((Segment(pnt[0], pt) * Segment(pnt[token], pt)) <= 0) { return true; } return false; } if (-1 == res) { return false; } return (Segment(pnt[mid], pt) ^ Segment(pnt[mid], pnt[mid + 1])) <= 0;}void ace(){ Point pt; int cnt; while (scanf("%d %d %d", &n, &m, &k) != EOF) { for (int i = 0; i < n; ++i) { scanf("%d %d", &pnt[i].x, &pnt[i].y); } sort(pnt, pnt + n, cmpXY); sort(pnt + 1, pnt + n, cmpPK); pnt[n] = pnt[0]; cnt = 0; while (m--) { scanf("%d %d", &pt.x, &pt.y); if (inPolygon(pt)) { ++cnt; } } puts(cnt >= k ? "YES" : "NO"); } return ;}int main(){#ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout);#endif ace(); return 0;}/*******************************************************************************Test Data...5 4 2 1 -1 1 2 0 4 -1 2 -1 -1 -2 -1 1 -1 0 1 2 3*******************************************************************************/