[백준 1688] 지민이의 테러 C++

1688번: 지민이의 테러

기하학, 선분 교차, 레이 캐스팅 알고리즘

---

1. 문제 해결 아이디어

 

많은 예외 케이스 때문에 10번넘게 틀린 문제...

오래 고민한 만큼 정이 들어버린 문제다..

 

[백준 17387] 선분 교차 2 C++

선분 교차 판정 알고리즘 참고 포스팅

 

 

다각형 내부의 점인지 판정해야 할 점이 총 3개이다.

 

A라는 점이 주어진 다각형 내부에 있는지 확인하려고 한다.

다각형의 모든 선분과 현재 점에서 양의 방향으로 매우 긴 선분(x축과 평행)과의 교차여부를 확인해야한다.

1. A점에서 양의 방향으로 무한히(문제에서 주어질 수 있는 최대 x의 좌표보다 크게) 긴 선분을 만든다. (해당 선분을 A선분 이라고 하자)
   • 중요한 점 :  A선분의 오른쪽 점의 y좌표는 'A의 y좌표값 +1' 이 되어야 한다.
   • 문제의 모든 좌표가 정수이므로 판정해야 할 점과 멀리 떨어진 점의 y좌표가 1만큼 차이나게 둔다면
     절대 꼭짓점이 겹치거나 직선이 겹치게 되어 교점을 가지게 되는 일이 발생하지 않는다
      
2. A점이 꼭짓점에 속한다면 다각형 내부의 점이다.
3. A점이 현재 다각형의 선분 위에 있다면 다각형 내부의 점이다.
4. A선분과 다각형의 선분의 교차여부를 판정해서 교차한다면 cnt를 1 증가시킨다.
5. cnt값이 홀수라면 A점은 다각형 내부의 점이다.

 

위 1번의 중요한 점을 지키지 않는다면 예외 상황이 발생한다.

다각형은 (1,1), (5,1), (5,5), (1,5) 점을 가진 정사각형이라고 하자.

A점을 (0,5), 현재 다각형의 선분은 (1,5), (5,5)라고 가정하자.

위와 같은 경우에 4번에서 교차여부를 판정하게 된다.

이때 1번을 지키지 않았다면 위 경우에 교차한다고 판정하여 cnt가 1 증가하게 된다.

(1,5), (1,1) 선분과 (5,5), (5,1) 선분도 A선분과 교차하기 때문에

총 cnt는 3이 되고 A점은 다각형 내부의 점이라고 판단하게 되는 대참사가 발생한다...

 

위와 같은 경우를 방지하기 위해서 y좌표를 1 증가시킨 것임을 알게되었다.

 

---

2. 코드

#include <iostream>
#include <vector>
 
using namespace std;
 
struct Point{
    long long x, y;
    bool operator<=(Point &p1){
        if(x == p1.x){
            return y <= p1.y;
        }
        return x <= p1.x;
    }
};
 
int N;
vector<Point> poly;
Point friends[3];
 
void input(){
    cin >> N;
    long long a, b;
    
    for(int i = 0; i < N; i++){
        cin >> a >> b;
        poly.push_back({a, b});
    }
    for(int i = 0; i < 3; i++){
        cin >> a >> b;
        friends[i] = {a, b};
    }
}
int CCW(const Point& p1, const Point& p2, const Point& p3){
    double res = (p1.x*p2.y + p2.x*p3.y + p3.x*p1.y) - \
                    (p2.x*p1.y + p3.x*p2.y + p1.x*p3.y);
    
    if(res > 0) return 1;   // 반시계
    else if(res < 0) return -1;     // 시계
    else return 0;
}
 
bool isline_intersect(Point &a, Point &b, Point &c, Point &d){
    int std1, std2;
    
    std1 = CCW(a, b, c) * CCW(a, b, d);
    std2 = CCW(c, d, a) * CCW(c, d, b);
    
    if(std1 <= 0 && std2 <= 0){
        if(std1 == 0 && std2 == 0){     //선분이 일직선인 경우
            if(b <= a) swap(a, b);
            if(d <= c) swap(c, d);
            
            return a <= d && c <= b;
        }
        else return true;   //일직선이 아니면 교차함
    }
    else return false;  //CCW가 같은 방향이 있으면 
}
 
int isSafe(Point &A){
    Point inf;
    inf.x = 1000000001;
    inf.y = A.y+1;
    
    int cnt = 0;
    
    for(int i = 0; i < N; i++){
        Point p1 = poly[i];
        Point p2 = poly[(i+1)%poly.size()];
        
        // 꼭짓점에 있는 경우
        if(p1.x == A.x && p1.y == A.y){
            return 1;
        }
        // A가 p1p2선분 위에 있는 경우
        else if(isline_intersect(A, A, p1, p2)){
            return 1;
        }
        
        if(isline_intersect(A, inf, p1, p2)) cnt++;
    }
    return cnt % 2;
}
 
int main(void){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    input();
 
    for(int i = 0; i < 3; i++){
        cout << isSafe(friends[i]) << "\n";
    }
}