[Python] 32823번 채굴권 분할

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

---

 

24/11/27

 

 

이전에 ICPC예선에서 해결했던 문제 중 하나이다. 태그에 선분 교차 판정이 들어있는데, 사실 그렇게 거창하게 할 필요는 없고, CCW를 여러 번 사용하여 홀짝성만 판단하면 충분히 해결할 수 있는 문제다.

---

 

문제 접근 방식:

 

 

먼저, 선분들의 좌표들이 모두 극좌표의 형식으로 주어져 있음에 유의해야한다.

 

극좌표에서 일반적인 직교좌표계로 변환하는 방법은 다음과 같다. 반지름이 $r$이라고 하고, 각도가 $\theta$라고 한다면(이때의 각도는 라디안으로 주어진다) 다음과 같다.

 

$$(x, y) = (r\cos \theta, r \sin \theta)$$

 

문제에서는 선분의 끝 점이 모두 원주 위에 놓여있으므로 반지름 $r$은 $1,000$이 되고, 각도는 호도법이 아니라 육십분법으로 주어져있으므로 radians함수를 통해 라디안으로 바꿔야 한다.

 

예제 입력 1을 잘 관찰해보면, 어떤 한 점이 어느 영역에 위치해있고, 그 영역과 인접한 영역에 또 다른 점이 위치해있다면 불가능하다는 사실을 관찰할 수 있다.(여기서 이야기하는 "인접하다"라는 뜻은 변과 변끼리 만남을 의미한다.)

 

이를 확장하면, 어느 영역 $A$와 $A$와 인접한 영역들 $B_1, B_2, \dots$가 있다면, $A$와 $B$들을 제외한 $B_1, B_2, \dots$와 인접한 영역 $C_1, C_2, \dots$들은 $A$를 소유하는 회사와 같은 회사가 소유하는 영역임을 확인할 수 있다.

 

즉, 두 영역이 인접하면 서로 다른 회사가, 두 영역이 두 번 인접하면 서로 같은 회사가, 세 번 인접하면 서로 다른 회사가, 이를 확장하면 두 영역이 짝수번 인접하면 서로 같은 회사가 소유하는 땅이고, 홀수번 인접하면 서로 다른 회사가 소유하는 땅임을 확인할 수 있다.

 

그러면 어떤 두 영역이 인접한지, 인접하지 않은지는 어떻게 판단할 수 있을까?

 

한 선분에 대해서 생각해보자.

 

선분의 양 끝점을 $R, S$라고 하고, 판단하는 두 점을 $P_1, P_2$라고 한다면, $P_1$과 $P_2$가 한 선분에 대하여 서로 다른 영역, 즉, 인접한 영역에 있다면 CCW를 했을 때의 두 값이 서로 다르게 나올 것이다.

 

즉, $\text{CCW}(P_1, R, S) \cdot \text{CCW}(P_2, R, S) < 0$이라면 한 선분에 대하여 서로 인접한 영역이 된다는 뜻이다.

 

이 과정을 모든 선분에 대해서 진행하면 짝수 번 인접하는지 홀수 번 인접하는지 확인할 수 있다.

 

최종적으로 짝수 번 인접한다면 'YES'를, 아니라면 'NO'를 출력하면 충분하다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 32823번 채굴권 분할
# CCW
import sys
input = sys.stdin.readline
from math import radians, sin, cos

def polar_to_cartesian(r, theta):
    return (r*cos(radians(theta/10)), r*sin(radians(theta/10)))
def Dir_vec(P1, P2):
    return (P2[0] - P1[0], P2[1] - P1[1])
def CCW(P, Q, R):
    A, B = Dir_vec(P, Q), Dir_vec(Q, R)
    S = A[0]*B[1] - A[1]*B[0]
    if S > 0: return 1
    elif S < 0: return -1
    else: return 0
def solve():
    lines = []
    for _ in range(int(input())):
        a, b = map(int, input().split())
        lines.append((polar_to_cartesian(1000, a), polar_to_cartesian(1000, b)))
    theta, r = map(int, input().split())
    P1 = polar_to_cartesian(r, theta)
    theta, r = map(int, input().split())
    P2 = polar_to_cartesian(r, theta)
    p = 0
    for line in lines:
        Q, R = line
        if CCW(P1, Q, R)*CCW(P2, Q, R) < 0:
            p += 1
    if p % 2 == 1:
        print('NO')
        return
    print('YES')
    return

solve()