백준 3878번: 점 분리 (Convex hull 겹침 판정)

문제링크: 3878번: 점 분리 (acmicpc.net)

3878번: 점 분리

이 문제는 좌표평면 상의 여러개 하얀 점과 검은 점들이 있을때, 이 점들을 직선으로 분류할 수 있는지 없는지 판단하는 문제이다. 데이터적으로 보면 여러개의 데이터를 points로 좌표평면 위에 할당하고 이 데이터들을 분류할때 linearly separable 할수 있는지를 판단하는 문제로도 응용할 수 있곘다.

 

먼저 좌표평면 상 두 개의 그룹을 분류한다고 치면, 한 그룹과 다른 그룹의 범위가 겹치지 않으면 될 것이라 유추 할 수 있다. 그러면 여기서 그룹의 범위를 어떻게 구할까? 지난번에 배운 convex hull 알고리즘을 사용하면, 각 그룹의 점들을 에워싸는 선형의 최소 범위의 다각형 모양이 나올 것이다. 그러면 흰 점의 convex hull과 검은 점의 convex hull을 구하고, 이 두 convex hull이 겹치는지 겹치지 않는지 판단하면 될 것이다. convex hull을 구하는 방법과 설명은 백준 1708번: 볼록 껍질 (tistory.com) 에서 확인할 수 있다.

 

그렇다면 convex hull이 겹치는지는 어떻게 판단할까? 먼저 두개의 convex hull의 각 선분을 서로서로 비교해 보면서 intersect()함수로 선분 교차 판정을 하면 겹치는 것을 판단할 수 있을 것이다. 선분 교차 판정은 지난번의 백준 2162번: 선분 그룹 (tistory.com) 에서 확인할 수 있다. 그러나 선분 교차만으로는 한개의 convex hull이 다른 convex hull 내부에 들어가 있는 경우를 잡아내지 못한다. 그 경우를 위해 inside()함수를 만들어 convex hull중 하나의 점이 다른 convex hull 내부에 있는지 판단했다. 만약 white convex hull이 black convex hull 내부에 있다면, white convex hull을 이루는 모든 점은 black convex hull 내부에 있을 것이므로 점 하나만으로 판단해도 문제없다.

 

inside()함수의 원리는 만약 한 점 a가 convex hull 내부에 있다면 점a에서 convex hull의 점들(b1, b2, b3, b4..)까지의 선분 (a-b1, a-b2), (a-b2, a-b3) 들을 ccw해가면 모든 ccw 값이 0보다 클 것이다. 왜냐하면 convex hull은 반시계 방향대로 점을 저장했기에 convex hull내부의 점에서 각 점에 선분을 이으면 모두 반시계 방향일 것이기 때문이다.

import sys
from functools import cmp_to_key

def bcmpccw(a,b): #벡터 base-a, base-b의 외적, ccw:1 cw:-1 0이면 a가 짧으면:1, 길면: -1 반환
    v1=[a[0]-bbase[0],a[1]-bbase[1]]
    v2=[b[0]-bbase[0],b[1]-bbase[1]]
    if (v1[0]*v2[1])-(v1[1]*v2[0])>0:
        return 1
    elif (v1[0]*v2[1])-(v1[1]*v2[0])<0:
        return -1
    else:
        if (v1[0]**2+v1[1]**2)>(v2[0]**2+v2[1]**2):
            return -1
        else:
            return 1

def wcmpccw(a,b): #벡터 base-a, base-b의 외적, ccw:1 cw:-1 0이면 a가 짧으면:1, 길면: -1 반환
    v1=[a[0]-wbase[0],a[1]-wbase[1]]
    v2=[b[0]-wbase[0],b[1]-wbase[1]]
    if (v1[0]*v2[1])-(v1[1]*v2[0])>0:
        return 1
    elif (v1[0]*v2[1])-(v1[1]*v2[0])<0:
        return -1
    else:
        if (v1[0]**2+v1[1]**2)>(v2[0]**2+v2[1]**2):
            return -1
        else:
            return 1

def ccw(a,b,c,d): #벡터 a-b, c-d의 외적 ccw:1 cw:-1 line:0
    v1=[b[0]-a[0],b[1]-a[1]]
    v2=[d[0]-c[0],d[1]-c[1]]
    return (v1[0]*v2[1])-(v1[1]*v2[0])

def intersect(a,b): #a: ((ax1,ay1),(ax2,ay2)) , b ((bx1,by1),(bx2,by2))선분 교차하는지 판단 a,b가 점일때도 가능
    ap1=a[0]
    ap2=a[1]
    bp1=b[0]
    bp2=b[1]
    accw=ccw(ap1,ap2,ap1,bp1)*ccw(ap1,ap2,ap1,bp2)
    bccw=ccw(bp1,bp2,bp1,ap1)*ccw(bp1,bp2,bp1,ap2)
    if accw==0 and bccw==0:
        if ap1 == ap2: #a가 점일떄
            if min(bp1[0],bp2[0]) <= ap1[0] <= max(bp1[0],bp2[0]) and min(bp1[1],bp2[1]) <= ap1[1] <= max(bp1[1],bp2[1]):
                return 1
            return 0
        if bp1 == bp2: #b가 점일때
            if min(ap1[0],ap2[0]) <= bp1[0] <= max(ap1[0],ap2[0]) and min(ap1[1],ap2[1]) <= bp1[1] <= max(ap1[1],ap2[1]):
                return 1
            return 0
        if min(ap1[0],ap2[0])<max(ap1[0],ap2[0])<min(bp1[0],bp2[0])<max(bp1[0],bp2[0]):
            return 0
        if min(ap1[1],ap2[1])<max(ap1[1],ap2[1])<min(bp1[1],bp2[1])<max(bp1[1],bp2[1]):
            return 0
        if min(bp1[0],bp2[0])<max(bp1[0],bp2[0])<min(ap1[0],ap2[0])<max(ap1[0],ap2[0]):
            return 0
        if min(bp1[1],bp2[1])<max(bp1[1],bp2[1])<min(ap1[1],ap2[1])<max(ap1[1],ap2[1]):
            return 0
        return 1
    elif accw==0 or bccw==0:
        if accw>0 or bccw>0:
            return 0
        return 1
    elif accw<0 and bccw<0:
        return 1
    return 0

def inside(point, convex): #point가 convex 내부인지 판단
    for i in range(len(convex)):
        if ccw(point, convex[i-1], point, convex[i]) <= 0:
            return 0
    return 1
        
N=int(sys.stdin.readline().rstrip())

for _ in range(N):
    n, m =map(int,sys.stdin.readline().rstrip().split())

    black = []
    white = []
    
    for _ in range(n):
        x, y = map(int,sys.stdin.readline().rstrip().split())
        black.append((x,y))

    for _ in range(m):
        x, y = map(int,sys.stdin.readline().rstrip().split())
        white.append((x,y))

    if n == 0 or m == 0:
        print('YES')
        continue

    black= sorted(black,key=lambda x:(x[1],x[0]))
    white = sorted(white,key=lambda x:(x[1],x[0]))
    bbase = black[0][:]
    wbase = white[0][:]
    del black[0]
    del white[0]

    black = sorted(black, key = cmp_to_key(bcmpccw), reverse = True)
    white = sorted(white, key = cmp_to_key(wcmpccw), reverse = True)

    bconvex = []
    wconvex = []
    bconvex.append(bbase)
    wconvex.append(wbase)
    if black:
        bconvex.append(black[0])
        if n >= 3:
            for i in range(1,n-1):
                new=black[i]
                if ccw(bconvex[-2],bconvex[-1],bconvex[-1],new)>0:
                    bconvex.append(new)
                    
                elif ccw(bconvex[-2],bconvex[-1],bconvex[-1],new)<0:
                    bconvex.pop()
                    while ccw(bconvex[-2],bconvex[-1],bconvex[-1],new)<=0:
                        bconvex.pop()
                    bconvex.append(new)
                    
                elif ccw(bconvex[-2],bconvex[-1],bconvex[-1],new)==0:
                    bconvex.pop()
                    bconvex.append(new)

    if white:
        wconvex.append(white[0])
        if m >= 3:
            for i in range(1,m-1):
                new=white[i]
                if ccw(wconvex[-2],wconvex[-1],wconvex[-1],new)>0:
                    wconvex.append(new)
                    
                elif ccw(wconvex[-2],wconvex[-1],wconvex[-1],new)<0:
                    wconvex.pop()
                    while ccw(wconvex[-2],wconvex[-1],wconvex[-1],new)<=0:
                        wconvex.pop()
                    wconvex.append(new)
                    
                elif ccw(wconvex[-2],wconvex[-1],wconvex[-1],new)==0:
                    wconvex.pop()
                    wconvex.append(new)

    ans = 0
    
    if len(bconvex) < 3 and len(wconvex) < 3: #convex가 안만들어짐
        for b in range(len(bconvex)):
            for w in range(len(wconvex)):
                if wconvex[w-1] == wconvex[w] and bconvex[b-1] == bconvex[b]:
                    continue
                if intersect((bconvex[b-1],bconvex[b]), (wconvex[w-1], wconvex[w])):
                    ans = 1
                    break
     
    else:
        for b in range(len(bconvex)):
            for w in range(len(wconvex)):
                if intersect((bconvex[b-1],bconvex[b]), (wconvex[w-1], wconvex[w])):
                    ans = 1
                    break

        if inside(wconvex[0], bconvex) == 1:
            ans = 1
        if inside(bconvex[0], wconvex) == 1:
            ans = 1
    
    if ans == 1:
        print('NO')
    else:
        print('YES')

 먼저 convex hull 알고리즘을 사용해 흰점을 이루는 wconvex, 검은점을 이루는 bconvex 의 convex hull 점들을 저장했다. 만약 wconvex, bconvex의 길이가 모두 3 이하라면 convex hull이 만들어지지 않았다는 뜻이므로 각각의 선분 교차 판정만 해주면 된다. 위에 설명한것처럼 intersect()함수는 선분 a와 b의 교차를 판정한다. 점과 선분도 판단할 수 있도록 함수를 만들었다. 점 a를 표현하고 싶으면 a의 시작 끝 좌표를 같게 대입하면 선분과 점 교차를 판정할 수 있다.

 

만약 a또는 b가 선분이 아니고 점이라면 (ap1 == ap2, bp1 == bp2) accw, bccw중 둘중 하나는 항상 0이 될 것이다. 둘중 하나가 0일때 나머지 하나는 점의 위치가 같으므로 무조건 양수가 되어 0을 return 할 것이다. 문제는 accw, bccw가 모두 0일때인데 이때는 점과 선분이 모두 한 직선 위에 있다는 뜻이다. 모두 한 직선 위에 있을때, 선분의 x, y범위 내에 점이 위치하면 그 선분 위에 위치한 것이므로 겹침 판정한다.

 

그렇게 bconvex와 wconvex의 서로의 모든 선분을 교차 판정하고, inside()함수로 wconvex의 한 점이 bconvex 내부에 있는지 판단, bconvex의 한 점이 wconvex 내부에 있는지 판단해주면 convex hull이 겹침을 판단 할 수 있다.