[Python] 백준 20149 선분교차 3

문제 링크 :https://www.acmicpc.net/problem/20149

 

1. 접근 방법

문제는 매우 간단하다. 두 선분의 끝점이 주어지고, 교차하는지 판별하면 된다.

하지만 이를 해결하기 위한 과정은 간단하지 않을 수 있다.

 

우선, 선분 교차와 관련하여 CCW 지식이 있으면 더욱 편하게 해결할 수 있다.

그리고 선분 위치에 따라 분류하여 작업을 진행해야 한다.

---

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/PS/blob/master/BAEKJOON/Python/20000/20100/20149.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

📕코드 해설

x1, y1, x2, y2 = MIIS()
x3, y3, x4, y4 = MIIS()
ccw1 = ccw(x1, y1, x2, y2, x3, y3)
ccw2 = ccw(x1, y1, x2, y2, x4, y4)
ccw3 = ccw(x3, y3, x4, y4, x1, y1)
ccw4 = ccw(x3, y3, x4, y4, x2, y2)

tmp1, tmp2 = ccw1 * ccw2, ccw3 * ccw4

우선, 주어진 점을 기반으로 ccw를 구한다. 이때, 각 선분을 기준으로 다른 두 점으로의 ccw를 구하고 이 값을 곱하게 된다. 이렇게 연산하는 것은 두 개의 ccw값을 곱함으로써 선분의 교차 여부를 판단할 수 있기 때문이다.

선분은 다음과 같은 4가지 경우의 수로 크게 나눌 수 있다.

1. 두 선분이 하나의 직선 위에 있으면서 교점이 있거나, 한 점을 공유하는 경우

  이 때, 두 개의 ccw값을 곱한 결과는 각각 0으로 나오게 된다.

2. 두 선분이 하나의 직선 위에 있지만, 교점이 없는 경우

  이 경우도 두 개의 ccw값을 곱한 결과는 각각 0이 나오게 되어 추가적인 확인이 필요하다.

3. 하나의 교점이 있게 교차하는 경우

  만약 왼쪽의 경우라면 ccw값을 곱했을 때 음수, 오른쪽의 경우라면 0이 나오게 된다.

4. 교점이 없는 경우

 

if not tmp1 and not tmp2:
	if (x1, y1) > (x2, y2):
		x1, y1, x2, y2 = x2, y2, x1, y1
	if (x3, y3) > (x4, y4):
		x3, y3, x4, y4 = x4, y4, x3, y3
	if (x1, y1) <= (x4, y4) and (x2, y2) >= (x3, y3):
		print(1)
		get_point((x1, y1), (x2, y2), (x3, y3), (x4, y4))
	else:
		print(0)

1, 2번 경우의 수를 먼저 확인한다. 두 경우 ccw를 곱한 결과가 0이 나오게 되어 if문에서 조건 분기를 한다.

그리고 교점을 더욱 수월하게 찾기 위하여 왼쪽 아래의 점, 오른쪽 위의 점으로 구분한다.

교점이 존재하는 조건은 선분의 양 끝점들을 비교하여 확인할 수 있고, 교점이 존재하면 1, 아니면 0을 출력한다.

get_point함수를 활용해서 교점을 출력하는데, 이 부분은 뒤에서 다시 확인해보겠다.

 

if tmp1 <= 0 and tmp2 <= 0:
	print(1)
	get_point((x1, y1), (x2, y2), (x3, y3), (x4, y4))
else:
	print(0)

3, 4번 경우의 수는 다음과 같이 처리한다.

3번 경우는 ccw를 곱한 결과가 음수 또는 0이 나오게 되어 if문에서 조건 분기가 되고, 바로 위에서 진행한 것처럼 교점이 있다면 1, 없으면 0을 출력한다.

 

def get_point(A: tuple, B: tuple, C: tuple, D: tuple):
    x1, y1 = A
    x2, y2 = B
    x3, y3 = C
    x4, y4 = D
    m = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4)
    if m:
        x = ((x1 * y2 - y1 * x2) * (x3 - x4) - (x1 - x2) * (x3 * y4 - y3 * x4)) / m
        y = ((x1 * y2 - y1 * x2) * (y3 - y4) - (y1 - y2) * (x3 * y4 - y3 * x4)) / m
        print(x, y)
    else:
        if B == C and A <= C:
            print(*B)
        elif A == D and C <= A:
            print(*A)

교점을 찾는 함수는 다음과 같이 구성했다.

위의 식이 나온 결과를 풀어 쓰면 다음과 같이 구할 수 있다.

우선, 두 선분을 직선이라 생각하고 직선의 방정식을 구한 후, 교점을 찾는다. 중간의 복잡한 계산과정은 생략을 했고, x, y 좌표는 가장 아래에 표시한 것처럼 구할 수 있다.

코드에서 m = (x1 - x2) * (y3 - y4) - (y1 - y2) * (x3 - x4) 부분은 x, y좌표의 공통분모이다. 이 값을 구한 것은 각 좌표 계산을 편하게 하려는 목적도 있지만, 같은 직선 위에 있는지 확인하는 용도로도 사용한다. 위에서 1번 조건과 3번 조건에서 모두 이 함수를 활용하였는데, 같은 방식을 사용하면 교점이 여러 개인 경우를 구할 수 없다. 그래서 한 직선 위에 있는지(그렇다면 m=0), 아닌지(m!=0)을 확인한다.

만약 한 직선에 있는것이 아니라면 x, y값을 계산하여 출력한다.

한 직선위에직선 위에 있고, 한 점을 공유하면 해당 점의 좌표를 출력한다. (한 점을 공유하되, 한 직선 위에 있는 경우는 위의 설명에서 생략함, 하지만 같은 방식으로 구할 수 있음)

---

3. 생각 정리

좌표 계산을 하고 경우를 나누는 것이 코딩보다는 수학에 조금 더 가까운 부분이라 생각이 되지만, ccw를 구하고 활용하는 부분 등은 이 문제를 통하여 배울 수 있는 것 같다.

예전에 ccw를 사용하지 않고 많이 고생했었는데, 그 기억과 과정도 많이 도움되었던 것 같다. 만약 이 글에서 주어진 방식이 어렵다면, 여러 조건을 확인하며 찬찬히 풀어보는 방법도 좋을 것 같다.