백준 1688 <지민이의 테러> C++

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

1688번: 지민이의 테러

---

일반적인 볼록 다각형이라면 단순히 모든 직선과 사람의 좌표를 CCW 알고리즘을 통해 일관된 방향이 나오는지 체크하면 되지만 오목 다각형을 포함하는 문제라면 그렇게 쉽게 풀리지 않습니다.

(0, 0) 에서 출발해서 시계 방향으로 체크한다고 가정하겠습니다. 

0~3 직선까지는 직선-점의 방향이 시계방향이지만 4 직선에서는 반시계방향인 것을 알 수 있습니다.

즉 오목 다각형을 포함하는 문제에서는 다른 방법으로 문제를 풀어야 합니다.

 

어떠한 점이 다각형의 내부에 존재하는가를 판단하는 일반적인 방법은 점에서 시작해 임의의 방향으로 무한히 뻗어나가는 임의의 반직선과 다각형이 교차하는 점의 수를 세는 것입니다.

일반적으로 교차점의 수가 홀수면 내부, 짝수면 외부라고 볼 수 있습니다.

 

임의의 점과 임의의 다각형이 좌표공간 내에 존재한다고 가정하겠습니다.

어떤 점이 다각형 내에 존재한다는 말은 다각형의 외부로 나가려면 임의의 선분을 거쳐야 한다는 말과 같습니다. 즉, 어느 방향으로 이동하던 선분이 존재합니다. 어떤 점에서 임의의 방향으로 반직선을 뻗으면 적어도 하나의 선분과 교차한다는 말과 같습니다.

 

우선 x 축과 평행하고 x 좌표가 증가하는 즉, y=point.x (x>=point.x) 의 반직선을 뻗겠습니다. 또 해당 반직선과 교차하는 선분의 수를 N 이라고 하겠습니다.

 

반직선과 다각형을 이루는 하나의 선분이 처음으로 교차했습니다. 점을 해당 선분의 너머로 이동시킨다면 점이 다각형의 외부에 있다면 내부로, 내부에 있다면 외부로 이동할 것입니다. 이는 선분이 다각형의 내부와 외부의 경계이기 때문에 자명한 사실입니다.

그럼 이동한 점에서 다시 반직선을 뻗는다면 교차하는 선분의 수는 앞서 이미 교차한 선분을 제외한 N-1 이 될 것입니다. 이런 방식으로 이동한 점에서 뻗은 반직선이 교차하는 선분의 수가 0 이 될 때 까지 이동시키면 해당 점은 다각형의 외부에 있게됩니다. 가장 처음에 언급했듯, 어느 방향으로 이동해도 선분이 존재해야 점이 임의의 다각형 내부에 존재하기 때문입니다.

 

그렇다면 위 과정을 거꾸로 거슬러 올라가보겠습니다.

 

N = 0 점이 다각형의 외부에 존재

-> 전에 교차한 선분을 다시 넘기

N = 1 점이 다각형의 내부에 존재

-> 전에 교차한 선분을 다시 넘기

N = 2 점이 다각형의 외부에 존재

...

N = 2K ( 짝수 ) 점이 다각형의 외부에 존재

N = 2K + 1 ( 음수 ) 점이 다각형의 내부에 존재

 

의 결론을 도출할 수 있게 됩니다.

 

결국 일반적으로 교차점의 수가 홀수면 내부, 짝수면 외부라고 볼 수 있습니다.

 

그렇기에 해당 문제를 풀 때 다각형을 이루는 임의의 선분 과 사람의 좌표에서 시작되는 임의의 반직선의 교차 횟수를 세주면 풀 수 있습니다.

다만 다음과 같이 반직선이 다각형의 모서리를 정확히 지날 때 (1) 와 반직선이 다각형을 이루는 선분을 포함할 때 (2) 사람의 좌표가 다각형을 이루는 선분위에 존재할 때(3) 가 문제가 됩니다.

 

우리는 탐색할 때 선분-반직선 쌍을 반복해 탐색하게 되는데, 모서리를 지날 때 (1) 의 경우 하나의 모서리에서 두 번 교차 판정을 내리기 때문에 정확한 판정을 방해하고, 다각형을 이루는 선분을 포함할 때 (2) 의 경우에도 역시 두 모서리를 무조건 지나게 되고 단순한 교차 판정만으로는 아래 두 경우를 판단할 근거가 없습니다.

또 사람의 좌표가 다각형을 이루는 선분위에 존재하는 경우 (3) 는 아래와 같이 반직선의 진행 방향에 따라 교차하는 선분의 수가 다르다는 문제가 있습니다.

따라서 약간의 트릭을 이용해 해당하는 세 경우를 겪지 않도록 하겠습니다.

사람의 좌표에서 임의의 아무 방향으로 반직선을 뻗어도 된다는 점과 우리는 정수 좌표 평면계에서 문제를 풀고 있다는 점을 이용하겠습니다.

 

반직선이 볼록 다각형의 모서리를 지나는 경우 (1) 를 제외시키려면 반직선이 시작과 끝을 제외한 어느 정수 좌표 평면을 지나지 않으면 됩니다. 또 끝점은 시스템상 한계를 벗어난 좌표, 즉 100,000,000 을 벗어난 좌표를 지정하면 됩니다. 즉, (100,000,000 + n, 시작점.y + 1) 을 끝점으로 두면 임의의 모서리가 해당 직선위에 있을 가능성이 없습니다.

 

반직선이 도형의 모서리를 포함하는 경우 (2) 는 위와 비슷하게 제외시킬 수 있는데, 역시 정수 좌표 평면의 그래프기 때문에 (100,000,000 + n, 시작점.y + 1) 를 끝점으로 두면 됩니다.

 

마지막으로 사람이 다각형을 이루는 선분 위에 존재할 때 (3) 의 경우에는 무조건 다각형 안에 존재하므로 예외처리를 해주면 됩니다.

---

 

#include <iostream>

#include <array>

#include <vector>

#include <algorithm>

#include <cmath>

#include <limits>

#include <map>

#include <deque>

using namespace std;

// 점을 저장할 구조체

struct Point {

    // 좌표

    long long int x;

    long long int y;

};

// ccw

long long int ccw(Point point_1, Point point_2, Point point_3) {

    // 포인트 어레이

    array<Point, 4> points = { point_1, point_2, point_3, point_1 };

    // ccw 값

    long long int ccw_sum = 0;

    // 계산

    for (int i = 0; i < 3; i++) {

        ccw_sum += points[i].x * points[i + 1].y;

        ccw_sum -= points[i].y * points[i + 1].x;

    }

    return ccw_sum;

}

// 직선 데이터를 저장할 구조체

struct Line {

    // 속한 점들

    Point point_1;

    Point point_2;

};

// 교차하는지 판단

bool is_cross(Line line_1, Line line_2) {

    // ccw

    long long int ccw_1 = ccw(line_1.point_1, line_1.point_2, line_2.point_1);

    long long int ccw_2 = ccw(line_1.point_1, line_1.point_2, line_2.point_2);

    long long int ccw_3 = ccw(line_2.point_1, line_2.point_2, line_1.point_1);

    long long int ccw_4 = ccw(line_2.point_1, line_2.point_2, line_1.point_2);

    // 곱한 값들 노말라이즈

    long long int norm_ccw_1 = ccw_1 > 0 ? 1 : ccw == 0 ? 0 : -1;

    long long int norm_ccw_2 = ccw_2 > 0 ? 1 : ccw == 0 ? 0 : -1;

    long long int norm_ccw_3 = ccw_3 > 0 ? 1 : ccw == 0 ? 0 : -1;

    long long int norm_ccw_4 = ccw_4 > 0 ? 1 : ccw == 0 ? 0 : -1;

    // 결과

    long long int result_1 = norm_ccw_1 * norm_ccw_2;

    long long int result_2 = norm_ccw_3 * norm_ccw_4;

    // 값의 곱이 모두 음수면 완벽한 교차

    if (result_1 < 0 and result_2 < 0) return true;

    // 값의 곱이 모두 양수면 교차하지 않음

    else if (result_1 > 0 and result_2 > 0) return false;

    // 값의 곱의 하나가 0 이고 나머지가 음수이면 교차

    else if ((result_1 == 0 and result_2 < 0) or (result_1 < 0 and result_2 == 0)) return true;

    // 값의 곱의 하나가 0 이고 나머지가 양수이면 교차하지 않음

    else if ((result_1 == 0 and result_2 > 0) or (result_1 > 0 and result_2 == 0)) return false;

    // 값의 곱의 하나가 양수이고 나머지가 음수이면 교차하지 않음

    else if ((result_1 > 0 and result_2 < 0) or (result_1 < 0 and result_2 > 0)) return false;

    // 나머지 ( 값의 곱이 모두 0 )

    else {

        // 두 선분이 같은 직선상에 있고 만나지 않을 때

        if ((((line_1.point_1.x > line_2.point_1.x and line_1.point_2.x > line_2.point_1.x) and

            (line_1.point_1.x > line_2.point_2.x and line_1.point_2.x > line_2.point_2.x)) or

            ((line_1.point_1.y > line_2.point_1.y and line_1.point_2.y > line_2.point_1.y) and

                (line_1.point_1.y > line_2.point_2.y and line_1.point_2.y > line_2.point_2.y))) or

            (((line_2.point_1.x > line_1.point_1.x and line_2.point_2.x > line_1.point_1.x) and

                (line_2.point_1.x > line_1.point_2.x and line_2.point_2.x > line_1.point_2.x)) or

                ((line_2.point_1.y > line_1.point_1.y and line_2.point_2.y > line_1.point_1.y) and

                    (line_2.point_1.y > line_1.point_2.y and line_2.point_2.y > line_1.point_2.y)))) return false;

        // 나머지

        else return true;

    }

}

int main(void) {

    // 입력

    int N;

    cin >> N;

    // 방어막 점들을 저장할 벡터

    vector<Point> points;

    for (int i = 0; i < N; i++) {

        Point point;

        cin >> point.x >> point.y;

        points.push_back(point);

    }

    // 시작 점 마지막에 추가

    points.push_back(points.front());

    // 사람 위치를 저장할 어레이

    array<Point, 3> people;

    for (int i = 0; i < 3; i++) {

        Point point;

        cin >> point.x >> point.y;

        people[i] = point;

    }

    // 사람 목록 순회

    for (int i = 0; i < 3; i++) {

        // 현재 사람

        Point person = people[i];

        // x 축으로 무한히 뻗은 반직선과 방어막이 교차하는 횟수

        long long int cnt_cross = 0;

        // 현재 사람에서 x 축으로 무한히 뻗은 반직선

        // 다각형의 어떤 변도 포함하지 않는 직선을 만들기 위해 기울기 조정

        // person.x -> 1000000000 (시스템상 최대 x) * 2 + 1 / person.y -> person.y + 1 을 지나는 직선에 포함되는 직선은 해당 범위의 정수 좌표계에선 만들 수 없음

        long long int max_x = 2000000001;

        long long int max_y = person.y + 1;

        Line person_line = { person, Point({max_x, max_y}) };

        // 방어막 점들이 지나는 직선 순회

        for (int i = 0; i < N; i++) {

            // 사람의 인덱스가 직선 위에 있으면 출력하고 패스

            if (person.x >= min(points[i].x, points[i + 1].x) and person.x <= max(points[i].x, points[i + 1].x) and

                person.y >= min(points[i].y, points[i + 1].y) and person.y <= max(points[i].y, points[i + 1].y) and

                ccw(points[i], points[i + 1], person) == 0) {

                cout << 1 << "\n";

                break;

            }

            // 직선 중 어느 점도 사람의 인덱스과 같지 않으면

            else {

                // 방어막 직선

                Line barrier_line = { points[i], points[i + 1] };

                // 교차하면 cnt + 1

                if (is_cross(person_line, barrier_line)) {

                    cnt_cross += 1;

                }

            }

            // 마지막 직선을 순회한 후

            if (i == N - 1) {

                // 교차하는 점의 수가 홀수이면 내부 / 짝수이면 외부

                if (cnt_cross % 2 == 0) {

                    cout << 0 << "\n";

                }

                else {

                    cout << 1 << "\n";

                }

            }

        }

    }

}