[BOJ 1688 // C++] 지민이의 테러

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 1688번 문제인 지민이의 테러이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/1688

1688번: 지민이의 테러

세 사람을 지키기 위한 꼭짓점이 N개인 다각형이 주어진다. 세 사람이 이 다각형의 내부에 있을 때(경계 포함), 각 사람은 안전하다고 말할 수 있다. 그러므로, 이 문제를 해결하기 위해서는 각 사람의 좌표가 주어진 다각형의 외부에 있는지 내부 또는 경계 위에 있는지를 확인해야 한다.

 

주어진 다각형이 볼록다각형이라는 보장이 없으므로, 주어진 점이 다각형 내부에 있는지를 확인하기 위해 Ray Casting 알고리즘을 이용하자. 

 

Ray Casting 알고리즘은 주어진 점에서 한 방향으로 무한한 (것과 같은 취급을 할 수 있는) 길이의 반직선을 그었을 때, 다각형의 변과 만나는 횟수를 세어 주어진 다각형의 내부에 있는지 외부에 있는지를 판단하는 알고리즘이다. 구체적으로, 만약 이 반직선과 다각형이 홀수번 만났다면 주어진 점은 다각형의 내부에 있는 것이고, 그렇지 않다면 주어진 점은 다각형의 외부에 있는 것이다.

 

Ray Casting 알고리즘에서 사용하는 반직선의 일부가 한 변과 무수히 많은 교점이 생기거나, 꼭짓점을 지나 한 점이 두 번 세어지는 일이 발생하면 반직선과 다각형의 변이 만나는 횟수를 제대로 셀 수 없게 된다. 이를 피하기 위하여 반직선을 정할 때 주어진 범위 내의 정수점으로 만들 수 없는 기울기의 직선을 잡으면 편하다.

 

그 외로, 다각형의 변과 반직선이 교차하는지를 판정해야하므로 CCW를 이용한 선분교차 판정법을 사용하였다.

 

Ray Casting 알고리즘은 주어진 점이 다각형의 경계 위에 있을 때에는 정상적으로 작동하지 않으므로(반직선의 방향에 따라 교점이 홀수개일수도, 짝수개일수도 있기 때문), 점이 다각형의 경계 위에 있는지는 별도로 검사해주자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

pll points[10001];

int CCW(pll A, pll B, pll C) {
    ll ccw = (B.first - A.first) * (C.second - A.second) - (B.second - A.second) * (C.first - A.first);
    if (ccw > 0) return 1;
    if (ccw < 0) return -1;
    return 0;
}

int intersection(pll A, pll B, pll C, pll D) {
    int ccw1 = CCW(A, B, C);
    int ccw2 = CCW(A, B, D);
    int ccw3 = CCW(C, D, A);
    int ccw4 = CCW(C, D, B);

    if (ccw1 * ccw2 == 0 && ccw3 * ccw4 == 0) {
        if (A > B) swap(A, B);
        if (C > D) swap(C, D);
        if (B < C || D < A) return 0;
        else return 1;
    }
    else if (ccw1 * ccw2 <= 0 && ccw3 * ccw4 <= 0) return 1;
    else return 0;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int N; cin >> N;
    for (int i = 0;i < N;i++) {
        ll x, y; cin >> x >> y;
        points[i] = { x,y };
    }
    points[N] = points[0];

    for (int i = 0;i < 3;i++) {
        int cnt = 0;
        ll x, y; cin >> x >> y;
        pll X = { x,y }, Y = { x + 1000000007, y + 1 }; // 선분 XY가 X에서 뻗어나가는 반직선 역할
        bool chk = 0;
        for (int j = 0;j < N;j++) {
            cnt += intersection(X, Y, points[j], points[j + 1]);
            if (CCW(points[j], X, points[j + 1]) == 0) { //다각형의 경계 위에 있는지 검사
                if ((points[j] <= X && X <= points[j + 1]) || (points[j + 1] <= X && X <= points[j])) {
                    chk = 1;
                    break;
                }
            }
        }
        if (chk) cout << 1 << '\n';
        else if (cnt & 1) cout << 1 << '\n';
        else cout << 0 << '\n';
    }
}