볼록껍질 내부 점 판정

김태성·2024년 6월 19일

알고리즘

목록 보기

21/30

요즘 계속 풀고있는 볼록껍질 관련 문제이다.
이번에는 볼록껍질 내부에 점이 있는지, 다른 볼록껍질과 충돌이 일어나는지 판단하는 문제이다.

점 분리

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 128 MB 3483 1013 676 27.457%
문제
평면 위에 여러 개의 검정 점과 흰 점이 있다. 이때, 길이가 무한대인 직선을 그어 흰 점과 검은 점을 분리하려고 한다. 직선은 어떤 점과도 만나면 안 된다. 직선으로 인해서 나누어지는 두 그룹 중 한 그룹에는 흰 점만 있어야 하고, 다른 그룹에는 검은 점만 있어야 한다.

아래 그림에서 제일 왼쪽 예제는 점선으로 표시된 직선으로 두 점을 나눌 수 있다. 하지만 나머지 예제는 직선으로 점을 분리할 수 없다.

흰 점과 검은 점의 좌표가 주어졌을 때, 직선으로 점을 분리할 수 있는지 없는지를 알아내는 프로그램을 작성하시오.

입력
첫째 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에 검정 점의 개수 n과 흰 점의 개수 m이 공백으로 구분되어 주어진다. n과 m은 100보다 작거나 같다. 다음 줄부터 n개의 줄에는 검정 점의 좌표가 공백으로 구분되어 주어진다. 그 다음 m개의 줄에는 흰 점의 좌표가 주어진다.

모든 점의 x, y좌표는 0보다 크거나 같고, 10000보다 작거나 같은 정수이다. 또한, 같은 위치에 점이 2개 이상 있는 경우는 없다.

출력
각각의 테스트 케이스에 대해서, 점을 문제의 설명대로 분리할 수 있으면 YES를, 아니면 NO를 출력한다.

import sys

def ccw(a,b,c):
    return (a[0]*b[1] + b[0]*c[1] + c[0]*a[1]) - (a[1]*b[0] + b[1]*c[0] + c[1]*a[0])

def isInside(lst,point) :
    if len(lst) <= 2:
        return True
    
    else:
        base = ccw(lst[0], lst[1], point)
        length = len(lst)
        for i in range(length) :
            cw = ccw(lst[i],lst[(i+1)%length],point)
            if cw * base <= 0: 
                return True
        return False


def check(a,b,c,d):
    if a > b:
        a,b = b,a
    if c>d:
        c,d = d,c
    
    return b<c or d<a

def cross(a,b,c,d):
    ab = ccw(a,b,c) * ccw(a,b,d)
    cd = ccw(c,d,a) * ccw(c,d,b)
    if ab==0 and cd==0:
        return not check(a[0],b[0],c[0],d[0]) and not check(a[1],b[1],c[1],d[1])
    return ab<=0 and cd<=0

def convexhull(points , color):
    points.sort()
    cal_1 = []
    cal_2 = []
    
    for i in range(color):
        while len(cal_1) > 1 and ccw(cal_1[-2] , cal_1[-1] , points[i]) <= 0:
            cal_1.pop()
        cal_1.append(points[i])

        while len(cal_2) > 1 and ccw(cal_2[-2] , cal_2[-1] , points[i]) >= 0:
            cal_2.pop()
        cal_2.append(points[i])
    
    cal_2.reverse()
    
    return cal_1[:-1] + cal_2[:-1]

T = int(sys.stdin.readline())
answer = []
for _ in range(T):
    B,W = map(int,sys.stdin.readline().split())
    
    Black = []
    White = []
    
    for b in range(B):
        x , y = map(int,sys.stdin.readline().split())
        Black.append([x,y])
        
    for w in range(W):
        x , y = map(int,sys.stdin.readline().split())
        White.append([x,y])
        
    if B > 1:
        Black = convexhull(Black, B)
    if W > 1:
        White = convexhull(White, W)

    B_len = len(Black)
    W_len = len(White)
    ans = True
    for i in range(B_len):
        if isInside(White,Black[i]) == False:
            ans = False
    for i in range(W_len):
        if isInside(Black,White[i]) == False:
            ans = False  
    
    for i in range(B_len):
        for j in range(W_len):
            if cross(Black[i],Black[(i+1)%B_len],White[j],White[(j+1)%W_len]):
                ans = False
    if ans:
        answer.append('YES')
    else:
        answer.append('NO')
    
for i in answer:
    print(i)

선분 교차판정 + 볼록껍질 + 볼록껍질 내부의 점 판정
3가지 알고리즘이 뒤섞였다.
볼록껍질은 이미 많이 다뤘으니 넘어가겠다.

선분 교차판정

우리는 두개의 선분이 어떻게 교차하는지 판단하는 과정을 이해해야 한다.

생각보다 간단하다.
두 점과, 다른 선분의 각 점을 ccw 연산을 하면 되는 것이다.
이는 ccw 설명에도 나와 있다.

복잡한 과정은 아니기에, 짧게 설명을 하고 넘어가자면

AB - C, AB - D , CD - A , CD - B 의 CCW를 구한다.
AB / CD 에서 구한 CCW의 곱이 음수가 된다면,이는 교차가 된다.

간단한 설명을 하자면, AB에서만 CCW를 구하게 되면, 교차하지 않아도 식이 성립하는 경우가 생기는데, 이때를 위해서 CD도 CCW를 구해준다.

이런 상황을 의미한다.
코드는 다음과 같다.

def check(a,b,c,d):
    if a > b:
        a,b = b,a
    if c>d:
        c,d = d,c
    
    return b<c or d<a

def cross(a,b,c,d):
    ab = ccw(a,b,c) * ccw(a,b,d)
    cd = ccw(c,d,a) * ccw(c,d,b)
    if ab==0 and cd==0:
        return not check(a[0],b[0],c[0],d[0]) and not check(a[1],b[1],c[1],d[1])
    return ab<=0 and cd<=0

간단하다. CCW를 구해서 0이 나온다면(평행하다면), 선분 위에 있는지 판단한다.

다음은 볼록껍질 내부의 점 판정이다.

	def isInside(lst,point) :
    if len(lst) <= 2:
        return True
    
    else:
        base = ccw(lst[0], lst[1], point)
        length = len(lst)
        for i in range(length) :
            cw = ccw(lst[i],lst[(i+1)%length],point)
            if cw * base <= 0: 
                return True
        return False

    for i in range(B_len):
        if isInside(White,Black[i]) == False:
            ans = False