#21 기하 - CCW(Counter-ClockWise) 1

2021. 8. 25. 14:28

CCW는 2차원 좌표 세 개를 주어진 대로 이었을 때 선분의 방향(시계, 반시계, 일직선)을 벡터의 외적 공식을 사용하여 구하는 알고리즘이다. 삼각형의 세 좌표가 주어질 때 넓이를 쉽게 구하기 위해 배웠던 신발끈 공식이 이것을 말한다. 이번에는 CCW를 활용하여 풀 수 있는 문제들에 대해 알아본다.

1. 다각형의 면적(https://www.acmicpc.net/problem/2166)

2차원 평면상에 다각형을 이루는 순서대로 N개의 좌표가 주어졌을 때 다각형의 넓이를 구하는 문제. CCW 알고리즘을 사용하면 간단하게 구할 수 있다.

예를들어 주어진 좌표가 (x1, y1), (x2, y2), (x3, y3), (x4, y4) 라고 할 때, 좌표를 아래와같이 나열한다.

그 다음 붉은색 선으로 이어진 수 끼리 곱한 값을 더한 값에서 파란색 선으로 이어진 수 끼리 곱한 값을 더한 값을 빼준 뒤 절댓값을 취하고 2로 나누면 위 좌표들로 구성된 다각형의 넓이가 된다. 이 공식을 사용하여 문제를 해결한 코드는 다음과 같다.

import sys

input = sys.stdin.readline


def sol2166():
    n = int(input())
    # 외적공식을 사용하기 위해 다각형을 이루는 좌표리스트 뒤에 첫 좌표를 덧붙여준다
    pos = [list(map(int, input().split())) for _ in range(n)]
    pos.append(pos[0])
    
    # 공식에 따라 값을 더한다
    res = 0
    for i in range(n):
        res += (pos[i][0] * pos[i+1][1] - pos[i+1][0] * pos[i][1])
        
    # 값에 절댓값을 취한 뒤 2로 나누어 소수 첫째자리까지 반환
    return '%.1f' % (abs(res)/2)

2. CCW(https://www.acmicpc.net/problem/11758)

2차원 평면상에 좌표 세개가 주어졌을 때, 좌표를 순서대로 이은 선분의 방향성이 반시계인지, 시계인지, 세 점이 일직선인지 구하는 문제. 조건문을 세세하게 나누어 모든경우를 따지면 공식을 몰라도 해결은 가능하지만 빼먹는 경우의 수가 생기기 쉽고 헷갈리는 탓에 생각보다 구현에 많은 시간이 걸렸다. 이 문제 또한 CCW 알고리즘으로 쉽게 해결할 수 있다.

import sys

input = sys.stdin.read


def sol11758():
	# 세 점의 좌표
    ax, ay, bx, by, cx, cy = map(int, input().split())
    
    # CCW 알고리즘 적용
    res = (ax*by + bx*cy + cx*ay) - (bx*ay + cx*by + ax*cy)
    
    # 결과값이 0이라면 일직선, 0보다 크다면 반시계방향, 작다면 시계방향
    return 0 if res == 0 else (1 if res > 0 else -1)

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

두 선분의 시작점과 끝점이 각각 주어졌을 때(이 때, 세 점이 일직선상에 놓여있는 경우는 없다.), 두 선분이 교차하는지 여부를 구하는 문제. 이 문제 또한 CCW 알고리즘으로 쉽게 해결할 수 있다.

CCW(X, Y, Z) 는 X Y Z를 잇는 선분이 반시계방향이라면 1, 시계방향이라면 -1, 세 점이 일직선상에 있다면 0이라 하자.

위 그림의 교차하는 선분 AB 와 CD를 보자. 선분 AB를 기준으로 CCW(A, B, C) 와 CCW(A, B, D)는 각각 시계방향, 반시계방향으로 반대의 방향성을 가진다. 선분 CD를 기준으로 CCW(C, D, A) 와 CCW(C, D, B) 를 봐도 마찬가지로 각각 반시계방향, 시계방향으로 반대의 방향성을 가진다.

이번엔 교차하지 않는 선분 AB와 CD를 보자. 선분 AB를 기준으로 CCW(A, B, C) 와 CCW(A, B, D)는 각각 시계방향, 반시계방향으로 반대의 방향성을 가지지만 선분 CD를 기준으로 CCW(C, D, A) 와 CCW(C, D, B) 를 보면 둘 다 반시계 방향으로 같은 방향성을 가진다.

서로 교차하지 않는 선분의 경우, 어느 한 선분 위의 모든 점은 반드시 다른 선분을 기준으로 한쪽방향에만 존재하게 된다. 그렇기 때문에 선분 AB 와 CD에 대해 CCW(A, B, C) * CCW(A, B, D) 와 CCW(C, D, A) * CCW(C, D, B) 중 어느 하나라도 1이라면 선분 AB 와 CD는 서로 교차하지 않는다고 할 수 있다. 그 외의 경우에는 선분 AB와 CD는 교차한다.(이 문제의 경우 세 점이 일직선상에 존재하는 경우가 없기 때문에 CCW는 반드시 1 또는 -1이므로 CCW가 0인 경우는 따질 필요가 없다) 이를 구현한 코드는 다음과 같다.

import sys

input = sys.stdin.read


def sol17387():
    # 네 점의 좌표
    x1, y1, x2, y2, x3, y3, x4, y4 = map(int, input().split())
    p1, p2, p3, p4 = [(x1, y1), (x2, y2), (x3, y3), (x4, y4)]
    
    # 선분 p1-p2 와 p3-p4를 각각 기준으로 한 CCW값의 곱
    v1, v2 = ccw(p1, p2, p3) * ccw(p1, p2, p4), ccw(p3, p4, p1) * ccw(p3, p4, p2)
    
    # 두 값중 하나라도 0보다 크다면 두 선분은 교차하지 않는다.
    if v1 > 0 or v2 > 0:
        return 0
        
    # 그 외의 경우 두 선분은 교차한다.
    return 1
    

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

4. 선분 교차 2(https://www.acmicpc.net/problem/17387)

선분 교차 1 문제와 조건 한가지를 제외하고는 완전히 동일하다. 이 문제에는 세 개 이상의 점이 일직선상에 놓이지 않는다는 조건이 없다. 즉, CCW 값이 0이 나올 경우를 상정해야 한다. 편의상 선분 교차 1 과 같이 CCW(A, B, C) * CCW(A, B, D) 와 CCW(C, D, A), CCW(C, D, B) 를 각각 v1, v2 라고 하자.

* 먼저, v1이나 v2 중 어느 하나가 0보다 클 경우 두 선분이 교차하지 않는다는 사실은 변하지 않는다.

if v1 > 0 or v2 > 0:
    return 0

* 그 다음으로 살펴봐야할 것은 세개 이상의 점이 일직선상에 놓이는 경우, 즉 v1또는 v2중 어느 하나라도 0이 되는 경우이다. (v1 == 0 or v2 == 0)

① 네 개의 점이 일직선상에 놓이는 경우 (V1 == V2 == 0)

② 세 개의 점이 일직선상에 놓이는 경우

① 케이스들의 경우, 결국 두 선분이 일직선상에 있지만 떨어져있는 경우(A <= B < C <= D 또는 C <= D < A <= B)를 제외하면 교차하는 경우라고 볼 수 있다. ② 의 세 번째 케이스는 네 점이 일직선상에 존재하지 않는데도 v1 == v2 == 0이 되는 특이한 케이스이다.

elif v1 == v2 == 0:
    return 0 if B < C or D < A else 1

② 의 첫 번째 케이스의 경우 v1이나 v2중 어느 것도 0보다 크지 않으며 v1과 v2가 모두 0이 아닌 경우, 즉 지금까지의 경우들을 배제하고 남은 기타 케이스에 포함된다. 이 경우 두 선분은 교차한다.

else:
    return 1

이에 따라 구현한 코드는 다음과 같다.

import sys

input = sys.stdin.read


def sol17387():
    # 선분을 이루는 네 점
    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)
    
    # 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과 떨어져있어 교차하지 않는 경우를 제외하면
        # 두 선분은 교차한다.
        return 0 if p2 < p3 or p4 < p1 else 1
        
    # 그 외의 경우 두 선분은 교차함
    else:
        return 1
    
   
# CCW 함수
def ccw(p1, p2, p3):
    res = (p1[0]*p2[1] + p2[0]*p3[1] + p3[0]*p1[1]) - (p2[0]*p1[1] + p3[0]*p2[1] + p1[0]*p3[1])
    return 1 if res > 0 else (-1 if res < 0 else 0)

이러한 잘 알려진 수학공식을 활용하는 문제들은 공식을 알고있다면 한없이 쉽지만 모른다면 아예 손도 대지 못하거나 풀더라도 많은 시간을 소비할 가능성이 높기 때문에 잘 기억해둘 필요가 있다.

'코딩테스트 > 알고리즘' 카테고리의 다른 글

#23 기하 - 원의 교차범위 면적 구하기 (0)	2021.08.28
#22 기하 - CCW(Counter-ClockWise) 2 (0)	2021.08.27
#20 트리 동적계획법 (0)	2021.08.23
#19 완전 탐색 - BFS(Breadth First Search) (0)	2021.08.21
#18 완전 탐색 - DFS(Depth First Search) (0)	2021.08.20

공부정리