[Python] 3878번 점 분리

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

---

 

23/10/06

 

 

이전에 볼록 껍질 문제를 쭉 푼 적이 있었는데, 그 때 해결 했던 문제 중 하나이다.

 

흥미로운 문제라고 생각되어 기록으로 남겨보고자 한다.

---

 

문제 접근 방식:

 

 

문제의 요구 사항은 검은 점과 흰 점을 오직 하나의 직선만으로 서로 분리할 수 있는지 판단하는 것이다.

 

검은 점끼리를 고무줄로 감싸고, 흰 점끼리를 고무줄로 감쌌을 때, 두 고무줄이 겹치지 않으면 가능하다고 판단했다.

 

여기서 볼록껍질이라는 말을 사용하지 않은 이유는 고무줄이라는 용어가 더 적합하다고 생각했기 때문이다.

 

볼록껍질은 고무줄이라는 말을 온전히 대변하지 않는다.

 

예를 들어, 두 점만 있는 경우 볼록 껍질을 정의하기가 어려운데, 고무줄은 정의할 수 있다.

 

한 점만 있는 경우도 마찬가지다. 작은 고무줄로 감싼다고 생각하면 되기 때문이다.

 

일반적으로 점이 여러 개 있는 경우, 고무줄로 감싸는 것은 볼록껍질을 만드는 것과 동일하기 때문에 그냥 구현할 수 있다.

 

점이 두 개인 경우나 한 개인 경우, 볼록껍질이라면 그 자체로 볼록껍질이 되기 때문에 예외처리를 해주면 된다.

 

두 볼록 껍질이 겹치는 것은, 한 볼록 껍질 안에 다른 볼록껍질의 점이 일부분 들어갈 때 겹친다고 말할 수 있으므로, 다각형 내부의 점이 있는지 판단하는 알고리즘을 구현했다.

 

맨 처음에는 다각형 내부의 점 판단 알고리즘을 $\mathcal{O}(\log n)$으로 구현하려고 이분 탐색을 사용했는데, 자꾸 오류가 나서 나이브하게 점 판단을 하도록 구현했다.($\mathcal{O}(n)$)

 

아마 이분 탐색을 사용해서 다각형 내부의 점 판단을 하도록 하는 문제가 따로 있었던 것으로 아는데, 이 문제에서는 해당이 안되는 것 같다.

 

점 두 개일 때의 경우를 따로 예외 처리하여 구현해야함에 유의하자.

---

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

# 3878번 점 분리
# 볼록 껍질, 볼록 다각형 내의 점 판단, 많은 조건 분기
'''
접근 방법:
검은점 흰점 따로 볼록껍질 후 각각에 대해서 내부 점 판단
'''
import sys
input = sys.stdin.readline

def D_sq(P1, P2): return (P1[0]-P2[0])**2 + (P1[1]-P2[1])**2
def Dir_v(Ps, Pe): return (Pe[0]-Ps[0], Pe[1]-Ps[1])
def cross(Va, Vb): return Va[0]*Vb[1] - Va[1]*Vb[0]

def CCW(P1, P2, P3):
    Va, Vb = Dir_v(P1, P2), Dir_v(P2, P3)
    K = cross(Va, Vb)
    if K > 0: return 1
    elif K == 0: return 0
    else: return -1

# P1P2와 P3P4가 만나는지의 여부
def Seg_meet(P1, P2, P3, P4):
    p = CCW(P1, P2, P3)*CCW(P1, P2, P4)
    q = CCW(P3, P4, P1)*CCW(P3, P4, P2)
    if p == 0 and q == 0:
        if P1 > P2: P1, P2 = P2, P1
        if P3 > P4: P3, P4 = P4, P3
        if P2 >= P3 and P1 <= P4: return 1
        else: return 0
    elif p <= 0 and q <= 0: return 1
    else: return 0

# P1P2와 P3가 만나는지 여부
def Seg_P_meet(P1, P2, P3):
    if CCW(P1, P2, P3) == 0:
        if P1 > P2: P1, P2 = P2, P1
        if P1 < P3 < P2: return True
        return False
    else: return False

# 모노톤 체인으로 구현한 컨벡스헐
def monotone_chain(point_li):
    point_li.sort()
    if len(point_li) <= 2: return point_li
    down_hull = [point_li[0], point_li[1]]
    up_hull = [point_li[0], point_li[1]]
    for i in range(2, len(point_li)):
        P3 = point_li[i]
        while len(down_hull) >= 2:
            P2 = down_hull.pop()
            P1 = down_hull[-1]
            if CCW(P1, P2, P3) > 0:
                down_hull.append(P2)
                break
        while len(up_hull) >= 2:
            P2 = up_hull.pop()
            P1 = up_hull[-1]
            if CCW(P1, P2, P3) < 0:
                up_hull.append(P2)
                break
        down_hull.append(P3)
        up_hull.append(P3)
    hull = down_hull + up_hull[len(up_hull)-2:0:-1]
    return hull

# 나이브한 내부 점 판단 알고리즘(hull이 삼각형을 잘 이룰때)
def P_in_polygon(hull, P):
    if P in hull:
        return True
    H = len(hull)
    for i in range(H):
        if CCW(P, hull[i], hull[(i+1)%H]) < 0:
            return False
    return True

# 두 헐이 존재하면 겹치는지 판단하는 알고리즘
def polygon_crash(hull1, hull2):
    H1, H2 = len(hull1), len(hull2)
    if H1 >= 3:
        if H2 >= 3:
            for i in range(H2):
                if P_in_polygon(hull1, hull2[i]):
                    return True
            for i in range(H1):
                if P_in_polygon(hull2, hull1[i]):
                    return True
            for i in range(H1):
                for j in range(H2):
                    if Seg_meet(hull1[i], hull1[(i+1)%H1], hull2[j], hull2[(j+1)%H2]):
                        return True
            return False
        elif H2 == 2:
            if P_in_polygon(hull1, hull2[0]) or P_in_polygon(hull1, hull2[1]):
                return True
            for i in range(H1):
                if Seg_meet(hull2[0], hull2[1], hull1[i], hull1[(i+1)%H1]):
                    return True
            return False
        else:
            return P_in_polygon(hull1, hull2[0])
    elif H1 == 2:
        if H2 >= 3:
            if P_in_polygon(hull2, hull1[0]) or P_in_polygon(hull2, hull1[1]):
                return True
            for i in range(H2):
                if Seg_meet(hull1[0], hull1[1], hull2[i], hull2[(i+1)%H2]):
                    return True
            return False
        elif H2 == 2:
            return Seg_meet(hull1[0], hull1[1], hull2[0], hull2[1])
        else:
            return Seg_P_meet(hull1[0], hull1[1], hull2[0])
    else:
        if H2 >= 3:
            return P_in_polygon(hull2, hull1[0])
        elif H2 == 2:
            return Seg_P_meet(hull2[0], hull2[1], hull1[0])
        else:
            return False

# 해설
def solve():
    N, M = map(int, input().rstrip().split())
    B_li = list(tuple(map(int, input().rstrip().split())) for _ in range(N))
    W_li = list(tuple(map(int, input().rstrip().split())) for _ in range(M))
    B_hull, W_hull = monotone_chain(B_li), monotone_chain(W_li)
    if polygon_crash(B_hull, W_hull):
        print('NO')
    else:
        print('YES')
    return

def main():
    T = int(input())
    for _ in range(T):
        solve()
    return

main()