20149: 선분 교차 3

시간 제한	메모리 제한
0.25초	512MB

문제

2차원 좌표 평면 위의 두 선분 L1, L2가 주어졌을 때, 두 선분이 교차하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있는 것도 교차하는 것이다.

L1의 양 끝 점은 (x1, y1), (x2, y2), L2의 양 끝 점은 (x3, y3), (x4, y4)이다.

 

입력

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다.

 

출력

L1과 L2가 교차하면 첫째 줄에 1, 아니면 0을 출력한다.

두 선분이 한 점에서 교차하는 경우 둘째 줄에 교차하는 점의 x좌표와 y좌표를 공백으로 구분해 출력한다. 한 점에서 교차하지 않는 경우에는 둘째 줄을 출력하지 않는다.

좌표의 절대/상대 오차는 10⁹까지 허용한다.

 

---

풀이

디버깅 지옥

 

우선 케이스 분리를 섬세하게 할 필요가 있다. 평면상에 두 선분의 위치 관계를 어떻게 나누어 볼 것인가. 그 방법도 굉장히 여러 가지인데 여기서는 코딩에 유리한 방법을 찾아야 한다. 이 케이스 분리만 6번 정도 시도해서 겨우 성공했다. 기하 문제의 가장 큰 어려움은 "맞왜틀(맞았는데 왜 틀렸지)"이 잘 안된다는 것이다. 실수를 줄이기 위해서는 빈틈없는 케이스 관리가 필수다.

 

처음에는 기울기가 다른 경우를 각 선분이 두 개의 축에 평행한 경우 4가지와 그렇지 않은 경우로 나누어 5가지 케이스로 두고 직선의 방정식을 이용해 구해보려 했으나 ccw를 활용해 선분이 교차하는지 판별하고 선분 끝이 닿는 경우만 따로 관리하는 것이 압도적으로 케이스 관리가 편했다.

 

먼저 기울기를 살펴보자. 두 선분은 기울기가 같은 경우와 다른 경우가 있다. 정확히는 외적으로 살펴볼 것인데 그 이유는 단순 기울기만 놓고 보면 평행인 직선의 일부인 경우와 일치하는 직선의 일부인 경우를 구분할 수 없다.

 

이렇게 ccw값으로 비교하면 두 선분이 만나지 않는 평행한 직선의 일부인 경우와 두 선분이 일치하는 직선의 일부인 경우를 구분할 수 있다. 게다가 두 선분의 기울기가 다른 경우는 직선상에서는 반드시 하나의 교점이 존재하게 되는데, 여기서 선분의 끝이 서로 접하는지를 구분하는 것도 가능하다. ccw값이 한쪽 끝에서만 0이라면 그 선분은 끝부분만 닿는다는 의미다.

 

그럼 ccw를 통해 케이스를 이렇게 나눠볼 수 있다.

 

두 선분이 일치하는 두 직선의 부분인 경우, ccw 값을 4번 구할 필요는 없다. 한 선분을 기준으로 다른 선분의 양 끝점의 ccw가 모두 0이라면 두 선분은 일치하는 직선의 부분이다.

 

구현할 부분을 나눠보면 이렇다.

1. CCW
2. ABC=0, ABD=0 인 경우, 끝점이 닿는지 판별하기
3. 교점이 존재하는 경우, 직선의 방정식 찾아 연립방정식으로 x, y 값 찾기
4. 교점이 존재하는 경우, y축에 평행한 선분의 x값을 다른 선분의 방정식에 대입해 x, y 값 찾기
5. 교점이 존재하고 CCW 값이 0인 점이 있는 경우 해당 점의 좌표 출력하기
6. 직선의 방정식으로 찾은 x, y 값이 선분 위의 점인지 판별하기

 

정답 코드

이 코드는 최적화, 가독성을 고려하지 않아서 매우 나쁜 코드라고 볼 수 있다.

import sys
input = sys.stdin.readline
p,q,r,s = map(int,input().split())
t,u,v,w = map(int,input().split())
a = (p,q)
b = (r,s)
c = (t,u)
d = (v,w)

minabx = min(a[0], b[0])
minaby = min(a[1], b[1])
maxabx = max(a[0], b[0])
maxaby = max(a[1], b[1])
mincdx = min(c[0], d[0])
mincdy = min(c[1], d[1])
maxcdx = max(c[0], d[0])
maxcdy = max(c[1], d[1])

def ccw(a,b,c):
    k = (a[1]-b[1])*(b[0]-c[0])-(a[0]-b[0])*(b[1]-c[1])
    if k > 0: return 1
    elif k < 0: return -1
    else: return 0

def sol():
    m_ab,m_cd,k_ab,k_cd = 0,0,0,0
    h_ab,h_cd = False,False
    x,y = 0,0

    if a[0] == b[0]:
        x = a[0]
        h_ab = True
    else:
        m_ab = (a[1] - b[1]) / (a[0] - b[0])
        k_ab = a[1] - (m_ab * a[0])

    if c[0] == d[0]:
        x = c[0]
        h_cd = True
    else:
        m_cd = (c[1] - d[1]) / (c[0] - d[0])
        k_cd = c[1] - (m_cd * c[0])

    if h_ab:
        y = m_cd * x + k_cd
    elif h_cd:
        y = m_ab * x + k_ab
    else:
        x = (k_cd - k_ab)/(m_ab - m_cd)
        y = m_ab * x + k_ab

    if ccw(a,b,c) == 0 and ccw(a,b,d) != 0:
        x,y = c
    elif ccw(a,b,c) != 0 and ccw(a,b,d) == 0:
        x,y = d
    elif ccw(c,d,a) == 0 and ccw(c,d,b) != 0:
        x,y = a
    elif ccw(c,d,a) != 0 and ccw(c,d,b) == 0:
        x,y = b

    if minabx <= x <= maxabx and mincdx <= x <= maxcdx and minaby <= y <= maxaby and mincdy <= y <= maxcdy:
        print(x,y)
    return

cross1 = ccw(a,b,c)*ccw(a,b,d)
cross2 = ccw(c,d,a)*ccw(c,d,b)

if ccw(a,b,c) == ccw(a,b,d) == 0:
    if minabx <= maxcdx and mincdx <= maxabx and minaby <= maxcdy and mincdy <= maxaby:
        print(1)
        if minabx != maxabx:
            if minabx == maxcdx:
                if a[0] > b[0]:
                    print(*b)
                else:
                    print(*a)
            elif maxabx == mincdx:
                if a[0] > b[0]:
                    print(*a)
                else:
                    print(*b)
        else:
            if minaby == maxcdy:
                if a[1] > b[1]:
                    print(*b)
                else:
                    print(*a)
            elif maxaby == mincdy:
                if a[1] > b[1]:
                    print(*a)
                else:
                    print(*b)
    else:
        print(0)
else:
    if cross1 <= 0 and cross2 <= 0:
        print(1)
        sol()
    else:
        print(0)