(3878) 점 분리

https://www.acmicpc.net/problem/3878

단계별로 풀어보기

51단계(기하 3) 4번째

 

 

 

분리축 이론에 의해 두 다각형이 겹치지 않는다면 최소 하나의 분리축이 있다고 한다.

검은 점과 흰 점 각각의 컨벡스 헐을 구한 뒤 두 볼록 다각형이 겹치는지 판별하면 된다. 두 볼록 다각형이 겹치는지 판별하는 방법은 각각의 변의 쌍에 대해 선분이 교차하는지 전부 확인하면 된다.

단 이렇게 하면 한 다각형 안에 다른 다각형이 완전히 포함되는 경우를 잡지 못한다. 따라서 모든 점을 합친 볼록 다각형을 만든 뒤, 이 다각형이 흰 점 또는 검은 점으로만 이루어져있는지 확인하여 맞으면 포함된 경우이므로 분리축을 만들 수 없다.

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
using namespace std;

struct Point{
  long x, y;
  long p, q;
  bool isblack;
  Point(int x1= 0, int y1= 0, bool isblack1= true): x(x1), y(y1), p(1), q(0), isblack(isblack1) {}
  
  void set(const Point &base){
    p= x-base.x;
    q= y-base.y;
  }

  bool operator <(const Point &A) const {
    if(q*A.p!=p*A.q)  return q*A.p<p*A.q;
    if(p*p+q*q!=A.p*A.p+A.q*A.q)  return p*p+q*q<A.p*A.p+A.q*A.q;
    if(y!=A.y)  return y<A.y;
    return x<A.x;
  }
};

inline long ccw(const Point &p1, const Point & p2, const Point & p3){
  return 1L*(p2.x-p1.x)*(p3.y-p1.y)-1L*(p3.x-p1.x)*(p2.y-p1.y);
}

vector<int> convexhull(vector<Point> &p){
  int sz= p.size();
  vector<int> res;
  res.reserve(sz);

  if(sz==1){
    res.push_back(0);
    return res;
  }else if(sz==2){
    res.push_back(0);
    res.push_back(1);
    return res;
  }

  sort(p.begin(), p.end());
  for(int i=1;i<sz;i++)  p[i].set(p[0]);
  sort(p.begin()+1, p.end());

  stack<int> s;
  s.push(0);  s.push(1);
  
  for(int i=2;i<sz;i++){
    while(s.size()>=2){
      int second= s.top();
      s.pop();
      int first= s.top();
        
      if(ccw(p[first],p[second],p[i])>0){
        s.push(second);
        
        break;
      }
    }

    s.push(i);
  }

  while(!s.empty()){
    res.push_back(s.top());
    s.pop();
  }
  res.push_back(res[0]);

  return res;
}

bool iscross(Point &p1, Point &p2, Point &p3, Point &p4){
  long a= ccw(p1,p2,p3)*ccw(p1,p2,p4);
  long b= ccw(p4,p3,p1)*ccw(p4,p3,p2);
  
  if(a==0 && b==0){
    pair<long, long> xy1= {p1.x, p1.y};
    pair<long, long> xy2= {p2.x, p2.y};
    pair<long, long> xy3= {p3.x, p3.y};
    pair<long, long> xy4= {p4.x, p4.y};
    
    return (min(xy1,xy2)<=max(xy3,xy4) && min(xy3,xy4)<=max(xy1,xy2));
  }else if(a<=0&&b<=0){
    return true;
  }else{
    return false;
  }
}

bool solve(){
  int n, m;
  
  cin >> n >> m;
  
  vector<Point> pblack, pwhite, p;
  pblack.reserve(n);  pwhite.reserve(m);  p.reserve(n+m);
  
  for(int i=0;i<n;i++){
    int x, y;
    
    cin >> x >> y;
    
    pblack.push_back(Point(x, y, true));
    p.push_back(Point(x, y, true));
  }
  for(int i=0;i<m;i++){
    int x, y;
    
    cin >> x >> y;
    
    pwhite.push_back(Point(x, y, false));
    p.push_back(Point(x, y, false));
  }
  
  vector<int> hullblack= convexhull(pblack);
  vector<int> hullwhite= convexhull(pwhite);
  
  for(int i=0;i<hullblack.size()-1;i++){
    for(int j=0;j<hullwhite.size()-1;j++){
      if(iscross(pblack[hullblack[i]], pblack[hullblack[i+1]], pwhite[hullwhite[j]], pwhite[hullwhite[j+1]])){
        return false;
      }
    }
  }
  
  vector<int> hullall= convexhull(p);
  bool black= false, white= false;
  
  for(int i=0;i<hullall.size();i++){
    if(p[hullall[i]].isblack)  black= true;
    else  white= true;
    
    if(black&&white)  return true;
  }
  
  return false;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int T;
  
  cin >> T;
  
  while(T--){
    cout << (solve() ? "YES\n" : "NO\n");
  }

  return 0;
}