[백준 BOJ] 20149 선분 교차 3 (python)

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

20149번: 선분 교차 3

선분 교차, 그 세번째 문제입니다.

참고로 4, 5는 다이아등급으로 풀지 못했습니다.. 

역시 CCW를 사용하지 않는 풀이와 사용하는 풀이 두가지로 풀이가 나뉘었습니다.

 

교차점

이번 문제에서는 두 선분이 한 점에서 교차할때 그 점의 좌표를 구하게 되는 문제입니다.

그러므로 선분 교차 2의 기본 코드에 점의 좌표를 구하는 코드만 추가하시면 됩니다.

그렇기 때문에 CCW를 쓰는 경우라도 교차점을 구하는 부분에서는 일차함수식을 써주었습니다.

다음은 두 일차함수에서 교차점을 구해주는 수식입니다.

 y = a1 * x + b1, y = a2 * x + b2 일때 ((b2 - b1) / (a1 - a2), a1 * (b2 - b1) / (a1 - a2) + b1)

단, y축과 평행한 선분의 경우 일차함수식을 구할 수 없으니 역시 케이스를 나눠주셔야 합니다.

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)
                    if l1[2] == l2[3]:
                        print(l1[0], l1[2])
                    if l1[3] == l2[2]:
                        print(l1[0], l1[3])
            else:
                if l1[2] - 0.001 <= l2[2] * l1[0] + l2[3] <= l1[3] + 0.001:
                    print(1)
                    print(l1[0], l2[2] * l1[0] + l2[3])
                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)
                    print(l2[0], l1[2] * l2[0] + l1[3])
                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)
                    if l1[2] == l2[2]:
                        if l1[0] == l2[1]:
                            print(l1[0], l1[2] * l1[0] + l1[3])
                        if l1[1] == l2[0]:
                            print(l1[1], l1[2] * l1[1] + l1[3])
                    else:
                        print((l2[3]-l1[3])/(l1[2]-l2[2]), l1[2] * (l2[3]-l1[3])/(l1[2]-l2[2]) + l1[3])
                else:
                    print(0)

 

역시 오차값 보정과 너무 많은 분기점때문에 코드가 좋다고는 할 수 없습니다.

따라서 이 문제 역시 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())
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)
        elif max(y1, y2) == min(y3, y4):
            print(1)
            print(x1, max(y1, y2))
        elif max(y3, y4) == min(y1, y2):
            print(1)
            print(x1, min(y1, y2))
        else:
            print(1)
    else:
        if max(x1, x2) < min(x3, x4) or max(x3, x4) < min(x1, x2):
            print(0)
        elif max(x1, x2) == min(x3, x4):
            print(1)
            if x1 > x2:
                print(x1, y1)
            else:
                print(x2, y2)
        elif max(x3, x4) == min(x1, x2):
            print(1)
            if x1 < x2:
                print(x1, y1)
            else:
                print(x2, y2)
        else:
            print(1)
else:
    print(1)
    if x1 == x2:
        a2 = (y4 - y3) / (x4 - x3)
        b2 = y3 - a2 * x3
        print(x1, a2 * x1 + b2)
    elif x3 == x4:
        a1 = (y2 - y1) / (x2 - x1)
        b1 = y1 - a1 * x1
        print(x3, a1 * x3 + b1)
    else:
        a1 = (y2 - y1) / (x2 - x1)
        b1 = y1 - a1 * x1
        a2 = (y4 - y3) / (x4 - x3)
        b2 = y3 - a2 * x3
        print((b2 - b1) / (a1 - a2), a1 * (b2 - b1) / (a1 - a2) + b1)

 

관련 글

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

[백준 BOJ] 11758 CCW (python)