[Python 3] BOJ - 1688 "지민이의 테러"

 # 문제 링크 : https://www.acmicpc.net/problem/1688

1688번: 지민이의 테러

 # 풀이 :

 개인적으로 이 문제의 핵심은 CCW라고 생각한다. CCW란 세 점의 좌표가 주어졌을 때 세 점이 놓인 방향이 반시계 방향인지, 시계 방향인지, 일직선 상인지 판별하는 알고리즘이다.

<그림 1. 세 점의 관계>

  현재 빨간점을 시작점으로 하고 파란점을 경유하면서 초록점을 끝점으로 하는 경로의 진행방향은 시계방향이다. 그런데 반대로 초록점을 시작점으로 하고 파란점을 경유하면서 빨간점을 끝점으로 하는 경로의 진행방향은 반시계방향이다. 파란점을 시작점으로 하고 초록점을 경유하고 빨간점을 끝점으로 하는 경로의 진행방향은 시계방향이다. 따라서 어떤 점을 시작점으로 하고 끝점으로 하느냐에 따라 경로의 진행방향이 바뀜을 알 수 있다.

 그런데 마지막 끝점에서 다시 시작점으로 가는 선을 긋게 되면 삼각형이 항상 성립함을 알 수 있다. 세 점이 주어졌을 때, 삼각형의 넓이를 구하는 공식은 이른바 사선 공식으로 알려져 있다. 그런데 사선 공식에는 연산 이후 절대값을 취한다. 그런데 방향성은 반시계, 혹은 시계인데 절댓값을 취하면 방향에 대한 정보가 사라지므로 절댓값을 취하면 안된다. 추가적으로 앞에 곱해주는 1/2은 양수값을 곱해주는 것이므로 방향성을 판별할 때는 굳이 곱하지 않아도 방향성을 판별하는 데는 영향을 주지 않는다.

<그림 2. 삼각형의 면적 공식(위), 방향성 판별 공식(아래)>

 

<그림 3. 그림 1의 사선공식 결과>

 그림 3에서 빨간점을 시작점으로 초록점을 끝점으로 하는 경우 dir = -23이고 초록점을 끝점으로 빨간점을 시작점으로 하는 경우 dir = 23이다. 그런데 dir이 음수면 항상 시계 방향이고 dir이 양수이면 항상 반시계 방향이다. 그렇다면 dir이 0인 경우는 어떻게 해석해야 할까? dir이 0이라는 경우는 s도 0이므로 삼각형의 면적이 0이라는 뜻이다. 따라서 세 점은 일직선 상에 위치한다. 따라서 방향성은 없다.

<그림 4. 다각형 내부 외부 판별>

  그림 4에서 초록색 외부 기준점에서 각각의 점에 선분을 그었을 때, 파란색 선분, 즉 내부의 점과 연결된다면 초록색 점과 내부의 점을 그은 선분과 다각형은 1번 만난다. 반대로 빨간색 선분, 즉 외부의 점과 연결된다면 초록색 점과 외부의 점을 그은 선분과 다각형은 2번 만난다. 그런데 몇가지 경우를 직접 해보면 항상 다각형과 홀수번 만난다면 그 선분은 내부의 점을 연결한 것이고, 다각형과 짝수번(0 포함) 만난다면 그 선분은 외부의 점을 연결한 것이다.

<그림 5. 다각형의 내부 외부 판별>

  그런데 그림 5의 경우는 그림 4처럼 반드시 짝수번 만난다고 해서 외부의 점과 연결된 것은 아니다. 즉, 내부 혹은 외부의 점과 일직선이 되면 정답을 구할 수 없으니 기준점을 설정할 때 절대로 다른 점과 일직선이 아닌 점을 설정해야 한다. 따라서 한 점과 다른 점을 이을 때 몇 번 만나는지 알아내야 한다

<그림 6. 두 선분의 교차여부>

 그림 6은 빨간 두 점으로 구성되는 선분과 파란 두 점으로 구성되는 선분이다. 위의 4가지 그림 중 첫번째와 두번째 그림은 양 선분이 모두 한 점에서 만나는 경우이고 세번째와 네번째의 경우는 만나지 않는 경우이다. 첫번째 그림은 파란 점으로 구성되는 선분에서 각각의 빨간점을 ccw를 한 결과이다. 두개의 화살표가 서로 다른 방향을 나타냄을 알 수 있다. 두번째 그림은 빨간점으로 구성되는 선분에서 각각의 파란점을 ccw한 결과이다. 역시 두개의 화살표가 다른 방향을 나타내고 있다. 즉, 2개의 선분이 있다면 한 선분(파란색 점끼리 이은 선분)을 먼저 고정시키고 고정시킨 선분의 양 끝점을 제외한 다른 두점(빨간 점 2개)을 ccw한 결과가 음수고 나머지 선분(빨간색 점끼리 이은 선분)을 고정시키고 고정시킨 선분의 양끝점을 제외한 다른 두 점(파란 점 2개)을 ccw한 결과도 음수가 나온다면 두 선분은 한 점에서 만난다.

 따라서 입력으로 주어지는 꼭짓점을 순서대로 리스트에 담고 마지막 꼭짓점과 첫점을 이은 선분을 고려해야 하므로 리스트에 첫 꼭짓점을 한번 더 담는다. 그 후, 각 사람의 좌표에 따라 현재 방어막을 이루는 선분과 사람의 좌표의 ccw가 0이라면, 즉 방어막의 선분과 사람이 일직선에 있다면 범위를 조사하여 방어막의 선분의 외부에서 일직선을 이루는지, 방어막의 선분 내부에서 일직선을 이루는지 조사한다. 

 만일 그렇지 않다면 외부의 기준점을 설정하여 외부 기준점과 현재 사람의 좌표를 잇는 선분과 방어막의 선분들의 교차여부를 조사하여 총 만나는 횟수가 짝수이면 그 사람은 방어막의 외부에 있고 홀수이면 그 사람은 방어막의 내부에 있으므로 정답을 구할 수 있다.

 

 # 코드

import sys, math

# Point 객체 : 점 (x,y)를 나타내는 객체
class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    # compare 함수 : 다른 Point 객체와의 비교함수. x가 작은순, x가 같다면 y가 작은 순으로 비교
    def compare(self, other):
        if self.x < other.x:
            return -1
        elif self.x == other.x:
            if self.y < other.y:
                return -1
            if self.y > other.y:
                return 1
            return 0
        else:
            return 1
            
# ccw : 점 a,b,c가 있을 때 방향성을 리턴하는 함수
#       (반시계 = 양수, 시계 = 음수, 일직선 = 0)
def ccw(a,b,c):
    return a.x * b.y + b.x * c.y + c.x * a.y - b.x * a.y - c.x * b.y - a.x * c.y

# judge : 선분 2개의 교점 여부를 리턴하는 함수
def judge(line1, line2):
    # p1, p2 : 첫번째 선분의 양 끝점
    p1 = line1[0]
    p2 = line1[1]
    
    # p3, p4 : 두번째 선분의 양 끝점
    p3 = line2[0]
    p4 = line2[1]
    
    res1 = ccw(p1, p2, p3) * ccw(p1, p2, p4)
    res2 = ccw(p3, p4, p1) * ccw(p3, p4, p2)
    return res1 < 0 and res2 < 0

# go : 한 점이 line으로 이루어진 다각형의 변과 짝수번 만나는지, 홀수번 만나는지 리턴하는 함수
def go(point, line):
    for i in range(n):
        t1 = ccw(line[i], line[i + 1], point)
        # 만일 세 점이 일직선이라면
        if t1 == 0:
            minx = min(line[i].x, line[i + 1].x)
            maxx = max(line[i].x, line[i + 1].x)
            miny = min(line[i].y, line[i + 1].y)
            maxy = max(line[i].y, line[i + 1].y)
            # 점이 선분의 일직선으로 내부에 있으려면 점의 x좌표와 y좌표가 모두
            # 선분의 최대 x좌표, 최소 x좌표, 최대 y좌표, 최소 y좌표의 범위에 있어야 함
            if minx <= point.x and point.x <= maxx:
                if miny <= point.y and point.y <= maxy:
                    # 모두 만족한다면 일직선의 내부에 있으므로 보호받을 수 있으므로
                    # 이후 과정을 생략하고 1 리턴
                    return 1
    # base : 기준점
    base = Point(1, 2147483647)
    
    # cnt : 기준점과 사람의 좌표를 이루는 선분이 다각형의 변과 몇번 만나는지 체크하는 변수
    cnt = 0
    for i in range(n):
        temp = [base, point]
        cnt += judge(temp, [line[i], line[i + 1]])
        
    # 짝수라면 0, 홀수라면 1리턴
    return cnt % 2

# 입력부
n = int(sys.stdin.readline())

# ans : 정답배열
ans = []

# line : 방어막의 꼭짓점들을 담는 배열
line = []

# 입력부
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    temp = Point(a,b)
    line.append(temp)
    
# 첫번째 꼭짓점을 다시 담아야 마지막 선분 처리 가능
line.append(line[0])

# m : 사람의 수
m = 3

# 세 사람의 좌표 입력 및 정답 저장
while m > 0:
    a, b = map(int, sys.stdin.readline().split())
    p1 = Point(a,b)
    ans.append(go(p1, n, line))
    m -= 1

# 정답 출력
for i in ans:
    print(i)