[BOJ 3878] 점 분리

문제

---

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

풀이

---

‘검은 점들과 흰 점들을 직선 하나로 분리할 수 있음’은 ‘검은 점들의 볼록 껍질과 흰 점들의 볼록 껍질이 disjoint하면서 포함 관계가 아님’과 동치이다.

‘두 볼록 껍질이 disjoint함’은 ‘모든 (검은 점들의 볼록 껍질의 한 변, 흰 점들의 볼록 껍질의 한 변) 쌍에 대해, 두 변이 서로 교차하지 않음’과 동치이다.

포함 관계는 한 볼록 껍질에서 아무 점이나 잡고 다른 볼록 껍질의 변들과 CCW를 계산함으로써 알 수 있다.

코드

---

import sys


def tangent(x, y):
    if x == a:
        return 1, y
    if x > a:
        return 0, (y - b) / (x - a), x
    if x < a:
        return 2, (y - b) / (x - a), x


def isline(x, y, z):
    return (y[1] - x[1]) * (z[0] - y[0]) == (z[1] - y[1]) * (y[0] - x[0])


def isintersect(x1, y1, x2, y2, x3, y3, x4, y4):
    p = (x2 - x1) * (y4 - y3) - (x4 - x3) * (y2 - y1)
    q = (x3 - x1) * (y4 - y3) - (x4 - x3) * (y3 - y1)
    r = (x3 - x1) * (y2 - y1) - (x2 - x1) * (y3 - y1)
    if p:
        return (p * q >= 0) and (abs(p) >= abs(q)) and (p * r >= 0) and (abs(p) >= abs(r))
    else:
        s = (x3 - x1) / (x2 - x1) if y1 == y2 else (y3 - y1) / (y2 - y1)
        t = (x4 - x1) / (x2 - x1) if y1 == y2 else (y4 - y1) / (y2 - y1)
        return q == 0 and r == 0 and (s <= 1 or t <= 1) and (s >= 0 or t >= 0)


for _ in range(int(sys.stdin.readline())):
    n, m = map(int, sys.stdin.readline().split())
    black = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
    white = [tuple(map(int, sys.stdin.readline().split())) for _ in range(m)]

    if n == m == 1:
        print('YES')
    
    elif (n, m) == (2, 1):
        x1, y1 = black[0]
        x2, y2 = black[1]
        if isline(black[0], black[1], white[0]) and ((min(x1, x2) < white[0][0] < max(x1, x2)) or (min(y1, y2) < white[0][1] < max(y1, y2))):
            print('NO')
        else:
            print('YES')
    
    elif (n, m) == (1, 2):
        x1, y1 = white[0]
        x2, y2 = white[1]
        if isline(black[0], white[0], white[1]) and ((min(x1, x2) < black[0][0] < max(x1, x2)) or (min(y1, y2) < black[0][1] < max(y1, y2))):
            print('NO')
        else:
            print('YES')
    
    elif (n, m) == (2, 2):
        if isintersect(*black[0], *black[1], *white[0], *white[1]):
            print('NO')
        else:
            print('YES')
    
    else:
        res = []
        for coord in [black, white]:
            if len(coord) == 1:
                res.append(coord)
                continue

            coord.sort(key=lambda x: (x[1], x[0]))
            a, b = coord.pop(0)
            coord.sort(key=lambda x: tangent(x[0], x[1]))

            stack = [(a, b), coord[0]]
            idx = 0
            while idx < len(coord) - 1:
                idx += 1
                w1, w2 = coord[idx]
                while len(stack) >= 2:
                    u1, u2 = stack[-2]
                    v1, v2 = stack[-1]
                    if (v1 - u1) * (w2 - v2) <= (v2 - u2) * (w1 - v1):
                        stack.pop()
                    else:
                        break
                
                stack.append((w1, w2))
                if (len(stack) >= 3) and (isline(stack[-3], stack[-2], stack[-1])):
                    stack.pop(-2)

            if len(stack) >= 3:
                if isline(stack[-2], stack[-1], stack[0]):
                    stack.pop()
            
            res.append(stack)

        flag = True
        if (n > 1) and (m > 1):
            for i in range(-1, len(res[0]) - 1):
                for j in range(-1, len(res[1]) - 1):
                    if isintersect(*res[0][i], *res[0][i + 1], *res[1][j], *res[1][j + 1]):
                        flag = False
                        break
                if not flag:
                    break

        if flag and (m > 1):
            px, py = res[0][0]
            for i in range(-1, len(res[1]) - 1):
                u1, u2 = res[1][i]
                v1, v2 = res[1][i + 1]
                if (u1 - px) * (v2 - py) < (v1 - px) * (u2 - py):
                    break
            else:
                flag = False

        if flag and (n > 1):
            px, py = res[1][0]
            for i in range(-1, len(res[0]) - 1):
                u1, u2 = res[0][i]
                v1, v2 = res[0][i + 1]
                if (u1 - px) * (v2 - py) < (v1 - px) * (u2 - py):
                    break
            else:
                flag = False

        if flag:
            print('YES')
        else:
            print('NO')