#22 기하 - CCW(Counter-ClockWise) 2

 이전 글에서 다루었던 CCW 알고리즘을 활용한 두 선분의 교차여부 검증의 응용문제에 대해 알아본다.

 

1. 선분 교차 3 (https://www.acmicpc.net/problem/20149)

 지난 게시글에서 다룬 선분 교차 2(https://www.acmicpc.net/problem/17387) 문제에 교차 여부만이 아닌 교점의 좌표까지 구해야하는 응용문제.  교차하는 경우 중에서도 교점이 한 개인 케이스와 여러 개인 케이스를 구분하고 교점이 한 개인 경우에도 교점의 좌표를 구하기 위해 따져야할 조건이 제법 많아 주의할 필요가 있는 문제이다.  이 문제를 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.read
INF = float('inf')


def sol20149():
    # 두 선분을 이루는 네 점의 좌표
    x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split())
    p1, p2, p3, p4 = [(x1, y1), (x2, y2), (x3, y3), (x4, y4)]
    
    # CCW 값의 곱
    v1, v2 = ccw(p1, p2, p3) * ccw(p1, p2, p4), ccw(p3, p4, p1) * ccw(p3, p4, p2)

	# 두 선분의 기울기
    try:
        a1 = (y2 - y1) / (x2 - x1)
    except:
        a1 = INF

    try:
        a2 = (y4 - y3) / (x4 - x3)
    except:
        a2 = INF

	# v1, v2 둘 중 하나라도 0 보다 크다면 두 선분은 교차하지 않음
    if v1 > 0 or v2 > 0:
        return 0
        
    # 셋 이상의 점이 일직선상에 존재하는 경우
    elif v1 == v2 == 0:
    	# p1 <= p2 , p3 <= p4 가 되도록 한다
        if p1 > p2:
            p1, p2 = p2, p1
        if p3 > p4:
            p3, p4 = p4, p3
            
        # 선분 l2의 점 중 선분 l1에 가장 가까운 점이 l1과 떨어져있는 경우
        # 두 선분은 교차하지 않음
        if p2 < p3 or p4 < p1:
            return 0
            
        # 그 외의 경우
        else:
        	# 두 선분의 기울기가 같고 선분의 끝부분에서 만나는 경우
            if a1 == a2:
                if p2 == p3:
                    return '\n'.join(['1', ' '.join(map(str, p2))])
                if p1 == p4:
                    return '\n'.join(['1', ' '.join(map(str, p1))])
                return 1
            # 두 선분의 기울기가 다르고 선분의 끝부분에서 만나는 경우
            # 또는 한 선분의 길이가 0인 경우(시작과 끝점이 같은 경우)
            else:
                p = p1 if p1 == p2 or p1 == p3 or p1 == p4 else p2 if p2 == p3 or p2 == p4 else p3 if p3 == p4 else p4
                return '\n'.join(['1', ' '.join(map(str, p))])
                
    # 반드시 한 점에서 교차하는 경우
    else:
    	# 두 선분의 기울기가 무한이 아닐 경우 일차방정식 그래프의 교점을 찾는 방식으로
        # 교점을 구한다.
        if a1 != INF and a2 != INF:
            k1 = -a1 * x1 + y1
            k2 = -a2 * x3 + y3
            resx = (k2 - k1) / (a1 - a2)
            if int(resx) == resx:
                resx = int(resx)
            resy = a1 * resx + k1
            if int(resy) == resy:
                resy = int(resy)
            return '\n'.join(['1', f'{resx} {resy}'])
            
        # 두 선분중 어느 하나의 기울기가 무한인 경우 교점 탐색
        else:
            if a1 == INF:
                resx = x1
                resy = a2 * resx - a2 * x3+ y3
            else:
                resx = x3
                resy = a1 * resx - a1 * x1 + y1

            if int(resx) == resx:
                resx = int(resx)
            if int(resy) == resy:
                resy = int(resy)
            return '\n'.join(['1', f'{resx} {resy}'])


# CCW 함수
def ccw(a, b, c):
    res = (a[0] * b[1] + b[0] * c[1] + c[0] * a[1]) - (b[0] * a[1] + c[0] * b[1] + a[0] * c[1])
    return 1 if res > 0 else -1 if res < 0 else 0

 

2. 선분 그룹 (https://www.acmicpc.net/problem/2162)

 시작점의 좌표와 끝 점의 좌표로 이루어진 선분의 정보가 N개 주어지고, 서로 교차하는 선분은 하나의 그룹이 된다고 할 때, 선분의 그룹의 갯수와 가장 큰 그룹의 크기를 구하는 문제.  선분 교차 여부의 검증은 ccw 알고리즘을 활용하여 해결 가능하며 선분의 그룹을 관리하는 것은 Disjoint Set 알고리즘(union-find 알고리즘)으로 해결 가능하다.  다만,

Python 의 경우 시간제한이 상당히 아슬아슬하기 때문에 상당한 최적화를 거치지 않으면 시간초과가 발생한다. 이를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline


def sol2162():
    # 선분의 갯수
    n = int(input())
    
	# 선분의 그룹을 관리하기 위한 union 리스트 
    u = [-1] * n
    
    # 선분들의 정보
    lines = [[*map(int, input().split())] for i in range(n)]
    
    # 선분 그룹의 갯수 - 선분의 갯수로 초기화
    cnt = n
    
    # 선분 리스트에서 두 선분을 뽑는 모든 경우의 수를 따져
    # 두 선분의 교차여부를 검증
    # 두 선분이 교차한다면 union 연산을 통해 그룹짓는다
    for i in range(n):
        for j in range(i+1, n):
            if cross_check(lines[i], lines[j]):
            	# union의 결과를 선분 그룹의 갯수에 반영
                cnt += union(u, i, j)
                
    # 선분 그룹의 갯수와 가장 큰 그룹의 크기 반환
    return str(cnt) + '\n' + str(-min(u))
        
    
# 선분의 교차 검증 함수
def cross_check(l1, l2):
    x1, y1, x2, y2 = l1
    x3, y3, x4, y4 = l2
    v1, v2 = ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4), ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2)
    return v1 <= 0 and v2 <= 0 and min(x1, x2)<=max(x3, x4) and min(x3, x4)<=max(x1, x2) and min(y1, y2)<=max(y3, y4) and min(y3, y4)<=max(y1, y2)
    
    
# CCW 함수
def ccw(x1, y1, x2, y2, x3, y3):
    res = (x2-x1) * (y3-y1) - (y2-y1) * (x3-x1)
    return 1 if res > 0 else -1 if res < 0 else 0


# union 연산
def union(u, a, b):
    a = find(u, a)
    b = find(u, b)
    if a != b:
        if u[a] < u[b]:
            u[a] += u[b]
            u[b] = a
        else:
            u[b] += u[a]
            u[a] = b
        return -1
    return 0
          
          
# find 연산
def find(u, x):
    if u[x] < 0:
        return x
    u[x] = find(u, u[x])
    return u[x]

CCW 함수와 선분의 교차검증 함수가 기존의 코드보다 간략하게 바뀐 것을 확인할 수 있다.