(1688) 지민이의 테러

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

단계별로 풀어보기

39단계(기하 2) 8번째

 

 

 

볼록다각형이라면 CCW를 각 선분+점에 적용해 부호가 전부 같으면 내부의 점이지만 이 문제에서는 볼록다각형이라는 보장이 없다.

다각형 내부의 한 점과 외부의 한 점을 이으면 이 선분은 다각형과 항상 홀수 번 만난다. 따라서 다각형 외부가 확실한 임의의 점을 잡아 가상의 선분을 만든 뒤, 다각형의 각 변과 선분 교차 판정을 하면 된다. 다만 아래 두 예외 케이스를 조심해야 한다.

1) 가상의 선분이 꼭지점과 만난다면 두 개의 선분과 교차 판정이 나게 된다. 따라서 기준을 잡고 다각형 변의 한쪽 끝점과 만날 땐 교차하지 않는다고 판정해야 한다. (예를 들어 y좌표가 큰 쪽의 점과 겹치는 경우에만 유효)

2) 변이 가상의 선분과 같은 직선 상에 있다면 (겹치든 안 겹치든) 내부/외부 판정 상태를 바꾸지 않으므로 교차하지 않는다고 판정해야 한다.

 

 

 

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

struct Cord{
  long x;
  long y;
  
  Cord(): x(0), y(0) {}
  Cord(long x0, long y0): x(x0), y(y0) {}
  
  bool operator <(const Cord& other) const{
    return make_pair(x,y)<make_pair(other.x,other.y);
  }
  bool operator <=(const Cord& other) const{
    return make_pair(x,y)<=make_pair(other.x,other.y);
  }
};

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n;
  
  cin >> n;
  
  vector<Cord> v(n+1), ob(3);
  
  for(int i=0;i<n;i++)  cin >> v[i].x >> v[i].y;
  v[n]= v[0];
  for(int i=0;i<3;i++)  cin >> ob[i].x >> ob[i].y;
  
  auto 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;
  };
  
  auto iscross= [&ccw](Cord &p1, Cord &p2, Cord &p3, Cord &p4){
    long a1= ccw(p1,p2,p3), a2= ccw(p1,p2,p4);
    long b1= ccw(p4,p3,p1), b2= ccw(p4,p3,p2);
    
    if(b1==0){
      if(min(p3,p4)<=p1 && p1<=max(p3,p4)){
        return -1;
      }else{
        return 0;
      }
    }else if(b2==0){
      return 0;
    }else if(a1==0){
      if(p1.y==p3.y && p3.x<=p1.x){
        return 1;
      }else{
        return 0;
      }
    }else if(a2==0){
      return 0;
    }else if(a1*a2<0&&b1*b2<0){
      return 1;
    }else{
      return 0;
    }
  };
  
  for(Cord point1:ob){
    int cnt= 0;
    Cord point0= {-1, point1.y};
    
    for(int i=0;i<n;i++){
      int x;
      
      if(v[i].y>v[i+1].y)  x= iscross(point1, point0, v[i], v[i+1]);
      else  x= iscross(point1, point0, v[i+1], v[i]);
      
      if(x<0){
        cnt= -1;
        break;
      }else{
        cnt+= x;
      }
    }
    
    cout << (cnt<0||cnt&1) << "\n";
  }
  
  return 0;
}