NKLAND - Mảnh đất tổ tiên

Tác giả: hieult

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define oo 1111111111
#define nmax 100111
#define MAX 222

using namespace std;

struct point{
     int x,y;
     bool operator == (point D) const{
          return (x == D.x && y == D.y);       
     }
};

point  a[nmax],b[nmax],p;
int n,m,N,test;

long long kc(point a,point b){
      long long X = (b.x-a.x);
      long long Y = (b.y-a.y);
      return X*X+Y*Y;
}

bool behon(point a,point b,point bn){
      long long ax,ay,bx,by;
      ax = a.x - bn.x;
      ay = a.y - bn.y;
      bx = b.x - bn.x;
      by = b.y - bn.y;
      if(ay!=0 && by==0) return true;
      if(ay==0||by==0) return false;
      return ax*by>ay*bx;
}

void Sort(point a[],int l,int r){
      int i = l,j = r;
      point mid = a[(l+r)/2];
      while(i<j){
           while(behon(a[i],mid,a[0])) i++;
           while(behon(mid,a[j],a[0])) j--;
           if(i<=j) swap(a[i++],a[j--]);
      }
      if(i<r) Sort(a,i,r);
      if(l<j) Sort(a,l,j);
}

int ccw(point p1,point p2,point p3){
      long long a1,a2,b1,b2,t;
      a1 = p2.x-p1.x;
      a2 = p3.x-p1.x;
      b1 = p2.y-p1.y;
      b2 = p3.y-p1.y;
      t = a1*b2-a2*b1;
      if(t==0) return 0;
      if(t>0) return 1;
      return -1;
}

int graham(point a[],int n){
      int m = 1;
      for(int i = 2;i<=n;i++)
           if(a[m].y>a[i].y) m = i;
      for(int i = 1;i<=n;i++)
           if(a[i].y==a[m].y && a[i].x>a[m].x) 
                m = i;
      swap(a[1],a[m]);
      a[0].x = a[1].x;
      a[0].y = a[1].y-1;
      Sort(a,2,n);
      a[++n] = a[1];
      m = 2;
      bool ok = true;
      for(int i = 3;i<=n;i++){
             ok = true;
             while(ccw(a[m],a[m-1],a[i])>=0){
                   if(ccw(a[m],a[m-1],a[1])==0){
                        ok = false;
                        if(kc(a[m],a[m-1])<kc(a[m-1],a[i]))
                              swap(a[m],a[i]);
                        break;      
                   }
                   else m--;    
             }
             if(ok) swap(a[++m],a[i]);
      }
      return --m;  
} 

long long stg(point a,point b,point c){
     long long s = (b.x-a.x)*1LL*(b.y+a.y)+(c.x-b.x)*1LL*(c.y+b.y)+ (a.x-c.x)*1LL*(a.y+c.y);
     return s>0?s:-s; 
}

int thuoc(point a,point b,point c){
               if(ccw(a,b,c)==0 && ((a.y<=c.y && c.y<=b.y)||(a.y>=c.y && c.y>=b.y))) return true;
               else return false;

}

int namtrong(point p,int l,int r,point b[]){
     while(r-l>2){
          int mid = (l+r+1)/2;
          int k = ccw(b[1],b[mid],p);
          if(k==0){
                if((b[1].x-p.x)*(b[mid].x-p.x)<0) return 1;;
                return 0;
          }
          if(k==1) l = mid-1;
          if(k==-1) r = mid;
     }
     point x,y,z;
     x = b[1];
     y = b[r];
     z = b[r-1];
     long long k = stg(x,y,z);
     long long t = stg(x,y,p)+stg(x,z,p)+stg(y,z,p);
     if(t>k) return 0;
     int kk = ccw(x,y,p)*ccw(x,z,p)*ccw(y,z,p);
     if(kk!=0) return 1;
     if(p==x||p==y||p==z) return 0;
     if(r==3){
           if(n<=3) return 0;
           if(ccw(x,y,p)==0)
                 return 1;
     }
     if(r==n &&ccw(x,z,p)==0)
          return 1;
     if(ccw(x,y,p)==0 && r!=n)
           return 1;
     if(ccw(x,z,p)==0 && r!=3)
           return 1;
     return 0;
}

int main(){
     //freopen("NKLAND.in","r",stdin);
     
     scanf("%d",&test);
     for(int itest = 1;itest<=test;itest++){
          bool flag = false;   
          scanf("%d",&n);
          for(int i = 1;i<=n;i++) scanf("%d %d",&a[i].x,&a[i].y);
          scanf("%d",&m);
          for(int i = 1;i<=m;i++) scanf("%d %d",&b[i].x,&b[i].y); 
          n = graham(a,n);
          m = graham(b,m);
          for(int i = 1;i<=n;i++){
                if(namtrong(a[i],1,m,b)){
                     flag = true;
                     break;
                }
          }
          if(!flag) for(int i = 1;i<=m;i++){
                if(namtrong(b[i],1,n,a)){
                     flag = true;
                     break;
                }
          }
          if(flag) printf("YES\n");
          else printf("NO\n");        
     }
    // getch();
}

Download