[BOJ 1688] 지민이의 테러

문제

---

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

풀이

---

주어진 다각형에 대해, 세 점이 다각형 내부에 있는지 외부에 있는지 판별하면 된다.

다각형이 오목 다각형일 수도 있으므로, CCW만을 이용해서 판별할 수 없다.

이럴 땐 점에서 다각형의 꼭짓점을 지나지 않는 반직선을 그어, 다각형의 변들과 홀수 번 만나는지 짝수 번 만나는지 세보면 된다.

추가로 점이 다각형의 변 위에 있을 때를 예외 처리해 줘야 한다.

코드

---

import sys


def ccw(x1, y1, x2, y2, x3, y3):
    return (x2 - x1) * (y3 - y2) - (x3 - x2) * (y2 - y1)


def isintersect(x1, y1, x2, y2, x3, y3, x4, y4):
    res1 = ccw(x1, y1, x2, y2, x3, y3)
    res2 = ccw(x1, y1, x2, y2, x4, y4)
    res3 = ccw(x3, y3, x4, y4, x1, y1)
    res4 = ccw(x3, y3, x4, y4, x2, y2)

    if res1 == res2 == res3 == res4 == 0:
        if (max(x1, x2) < min(x3, x4)) or (max(x3, x4) < min(x1, x2)) or (max(y1, y2) < min(y3, y4)) or (max(y3, y4) < min(y1, y2)):
            return 0
        else:
            return 1

    elif (res1 * res2 <= 0) and (res3 * res4 <= 0):
        return 1
    return 0


n = int(sys.stdin.readline())
coord = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]

for _ in range(3):
    x, y = map(int, sys.stdin.readline().split())
    z, w = x + 1, y + 1000000001
    meet = 0
    for i in range(-1, n - 1):
        if ccw(x, y, *coord[i], *coord[i + 1]) == 0:
            x1, y1 = coord[i]
            x2, y2 = coord[i + 1]
            if (min(x1, x2) <= x <= max(x1, x2)) and (min(y1, y2) <= y <= max(y1, y2)):
                print(1)
                break
        meet += isintersect(x, y, z, w, *coord[i], *coord[i + 1])
    else:
        print(meet % 2)