[백준 BOJ] 17386 17387 선분 교차 1, 2 (python)

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

17386번: 선분 교차 1

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

17387번: 선분 교차 2

요새 재밌게 풀이한 기하학 문제인 선분 교차 시리즈의 1, 2번 문제입니다.

두가지 풀이가 있는데 바로 저번에 풀었던 CCW를 쓰고 안쓰냐의 차이의 풀이입니다.

만약 CCW를 모르신다면 이전 글을 보시거나 11758번 문제 CCW를 풀어보시고 오시길 추천드립니다.

[백준 BOJ] 11758 CCW (python)

 

선분 교차 1

이번 두 문제는 단순히 두 선분의 교차 여부를 묻는 문제입니다.

그 중 이번 첫 문제는 두 선분의 양 끝 점중 어느 세 점 일직선 위에 없는 경우입니다.

 

우선 처음에는 선분이기에 일차함수식을 생각하며 풀었습니다.

다만 y축과 평행한 선분의 경우 일차함수로 표현할 수 없어 케이스를 따로 빼서 총 네가지 케이스로 풀이를 진행하였습니다.

x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())
if x1 != x2 and x3 != x4:
    a1 = (y1 - y2) / (x1 - x2)
    a2 = (y3 - y4) / (x3 - x4)
    b1 = y1 - a1 * x1
    b2 = y3 - a2 * x3
    if (a1 * x3 + b1 - y3) * (a1 * x4 + b1 - y4) <= 0 and (a2 * x1 + b2 - y1) * (a2 * x2 + b2 - y2) <= 0:
        print(1)
    else:
        print(0)
elif x1 == x2 and x3 != x4:
    a2 = (y3 - y4) / (x3 - x4)
    b2 = y3 - a2 * x3
    if min(y1, y2) <= a2 * x1 + b2 <= max(y1, y2) and min(x3, x4) <= x1 <= max(x3, x4):
        print(1)
    else:
        print(0)
elif x1 != x2 and x3 == x4:
    a1 = (y1 - y2) / (x1 - x2)
    b1 = y1 - a1 * x1
    if min(y3, y4) <= a1 * x3 + b1 <= max(y3, y4) and min(x1, x2) <= x3 <= max(x1, x2):
        print(1)
    else:
        print(0)
else:
    print(0)

 

다음은 CCW 알고리즘을 사용한 풀이입니다.

사실 시간에는 큰 차이가 없지만 더 간단하고 아마 문제가 의도하는 풀이는 이것에 더 가까울 것이라고 생각합니다.

어느 세 점도 일직선 위에 없기에 CCW가 0이 되는 경우는 없습니다.

L1의 두 끝 점이 L2를 포함한 직선에 의해 양쪽으로 나뉘고, 반대로 L2의 두 끝 점이 L1를 포함한 직선에 의해 양쪽으로 나뉘는 경우 두 선분이 교차한다고 할 수 있습니다.

이는 한 선분의 두 점에서 다른 선분의 각 끝 점으로의 CCW를 계산하고 두 값이 다른 것으로 판별이 가능합니다.

 

def CCW(p1_x, p1_y, p2_x, p2_y, p3_x, p3_y):
    ccw = (p2_x-p1_x)*(p3_y-p1_y)-(p3_x-p1_x)*(p2_y-p1_y)
    if ccw:
        ccw //= abs(ccw)
    return ccw
    
x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())
L1 = CCW(x1, y1, x2, y2, x3, y3) * CCW(x1, y1, x2, y2, x4, y4)
L2 = CCW(x3, y3, x4, y4, x1, y1) * CCW(x3, y3, x4, y4, x2, y2)
if L1 == -1 and L2 == -1:
    print(1)
else:
    print(0)

 

선분 교차 2

이번에는 첫번째 문제와 같지만 주어지는 점들이 일직선 상에도 있는 경우가 있습니다.

두번째 문제부터는 일차함수를 구해서 풀이를 하는 경우 작은 오차값들을 보정해주어야만 문제풀이가 가능했습니다.

참고로 이번 풀이는 이후의 문제들에도 적용하기 위해 여러 선분이 들어오는 경우를 가정하여 문제풀이를 진행하였습니다.

lines = []
for _ in range(2):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        lines.append((x1, x2, min(y1, y2), max(y1, y2)))
    else:
        a = (y2-y1)/(x2-x1)
        b = y1-a*x1
        lines.append((min(x1, x2), max(x1, x2), a, b))
lines.sort(reverse=True)
while lines:
    l1 = lines.pop()
    if l1[0] == l1[1]:
        for l2 in lines:
            if l2[0] > l1[0]:
                print(0)
                break
            if l2[0] == l2[1]:
                if l1[2] > l2[3] or l1[3] < l2[2]:
                    print(0)
                else:
                    print(1)
            else:
                if l1[2] - 0.001 <= l2[2] * l1[0] + l2[3] <= l1[3] + 0.001:
                    print(1)
                else:
                    print(0)
    else:
        for l2 in lines:
            if l2[0] > l1[1]:
                print(0)
                break
            if l2[0] == l2[1]:
                if l2[2] - 0.001 <= l1[2] * l2[0] + l1[3] <= l2[3] + 0.001:
                    print(1)
                else:
                    print(0)
            else:
                s = max(l1[0], l2[0])
                e = min(l1[1], l2[1])
                s_y = l1[2] * s + l1[3] - l2[2] * s - l2[3]
                s_e = l1[2] * e + l1[3] - l2[2] * e - l2[3]
                if s_y * s_e <= 0.001:
                    print(1)
                else:
                    print(0)

 

이번에도 CCW 알고리즘을 알고 다시 풀이한 풀이가 있습니다.

일차함수와 다르게 오차값을 생각해주지 않아도 풀이가 가능하고 앞선 문제와 같이 더 간단한 풀이가 가능합니다.

첫번째 문제와는 반대로 L1의 두 끝 점이 L2를 포함한 직선의 한 쪽에 몰려있고, L2의 두 끝 점이 L1를 포함한 직선의 한 쪽에 몰려있는 경우 두 선분은 교차를 하지 않는다고 할 수 있습니다.

위와 반대로 CCW를 계산한 두 값이 같은 것으로 이를 판별할 수 있습니다.

이번에는 CCW가 0이 되는 경우가 있기에 이런 식으로 경우를 나눠주었습니다.

그 중 네 점이 모두 한 직선에 있다고 볼 수 있는 모든 CCW가 0이 될 때 다시 경우가 나뉘게 됩니다.

두 선분이 같은 직선상에 있는 경우는 두 선분이 교차하는 경우와 교차하지 않는 두 경우가 모두 존재합니다.

이 부분에서는 이전 다른 풀이와 마찬가지로 직선이 y축과 평행한 경우는 y값을 비교하여  두 경우를 나눠주고, 아닌 경우에는 x값을 비교하여 두 경우를 나눠주었습니다.

def CCW(p1_x, p1_y, p2_x, p2_y, p3_x, p3_y):
    ccw = (p2_x-p1_x)*(p3_y-p1_y)-(p3_x-p1_x)*(p2_y-p1_y)
    if ccw:
        ccw //= abs(ccw)
    return ccw

x1, y1, x2, y2 = map(int, input().split())
x3, y3, x4, y4 = map(int, input().split())
ccw3 = CCW(x1, y1, x2, y2, x3, y3)
ccw4 = CCW(x1, y1, x2, y2, x4, y4)
ccw1 = CCW(x3, y3, x4, y4, x1, y1)
ccw2 = CCW(x3, y3, x4, y4, x2, y2)
if ccw1 * ccw2 == 1 or ccw3 * ccw4 == 1:
    print(0)
elif ccw1 == 0 and ccw2 == 0:
    if x1 == x2:
        if max(y1, y2) < min(y3, y4) or max(y3, y4) < min(y1, y2):
            print(0)
        else:
            print(1)
    else:
        if max(x1, x2) < min(x3, x4) or max(x3, x4) < min(x1, x2):
            print(0)
        else:
            print(1)
else:
    print(1)