(20670) 미스테리 싸인

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

단계별로 풀어보기

51단계(기하 3) 6번째

 

 

 

어떤 볼록 다각형의 점이 반시계 방향으로 정렬되어 있다면 반시계 방향으로 각 변과 내부의 한 점을 ccw 했을 때 항상 양수(왼쪽에 있음)가 나온다. 반대로 하나라도 음수가 나온다면 외부에 있는 것이다. 하지만 이 방식으로 풀면 O(K*(N+M))이 걸리므로 시간 초과가 난다.

어떤 볼록 다각형에 대해 처음 점을 기준으로 다른 모든 점으로 뻗어나가는 반직선을 그렸다고 하자. CCW로 임의의 점이 반직선 왼쪽인지 오른쪽인지 판별할 수 있으며, 이분탐색으로 반복하면 임의의 점이 어떤 이웃한 두 꼭지점 사이 반직선 영역에 존재하는지 알 수 있다. 이웃한 두 꼭지점과 임의의 점으로 CCW를 하면 이분탐색에 필요한 O(log N)만으로 내부 외부 판정을 할 수 있다.

 

 

 

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

struct Cord{
  long x;
  long y;
};

int ccw(Cord p1, Cord p2, Cord p3){
  long t= (p2.x-p1.x)*(p3.y-p1.y)-(p3.x-p1.x)*(p2.y-p1.y);
  
  if(t>0)  return 1;
  else if(t<0)  return -1;
  else  return 0;
}

bool isinside(vector<Cord> &v, Cord p){
  int sz= v.size();
  
  if(ccw(v[0], v[1], p)<0)  return false;
  if(ccw(v[0], v[sz-1], p)>0)  return false;
  
  int l= 1, r= sz-1;
  while(l+1<r){
    int mid= (l+r)/2;
    
    (ccw(v[0], v[mid], p)>0 ? l : r)= mid;
  }
  
  return ccw(v[l], v[l+1], p) > 0;
}

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

  int n, m, k;
  
  cin >> n >> m >> k;
  
  vector<Cord> a(n), b(m), t(k);
  
  for(int i=0;i<n;i++)  cin >> a[i].x >> a[i].y;
  for(int i=0;i<m;i++)  cin >> b[i].x >> b[i].y;
  for(int i=0;i<k;i++)  cin >> t[i].x >> t[i].y;
  
  int cnt= 0;
  
  for(int i=0;i<k;i++){
    cnt+= (!isinside(a, t[i]) || isinside(b, t[i]));
  }
  
  cout << (cnt ? to_string(cnt) : "YES");

  return 0;
}