BaekJoon 20149번 : 선분 교차 3 (python)

📝 BaekJoon 20149번 : 선분 교차 3 (P4 21.497%)

---

🔎 선분 교차 3 문제

---

📌 아이디어

ccw를 이용한 선분 교차를 좌표를 직접구해서 출력하고 기울기가 같으며 한 점에서 겹치는 경우를 예외처리 해주어야 하는 문제이다.

---

💭 풀이

• 선분 교차1,2의 코드를 그대로 이어 받아오면 ccw를 통한 교차 확인까지는 이미 완성되어 있다. 다만 교차는 되어 있지만 한 점에서 교차하지 않는 경우 즉 겹쳐 있는 경우는 좌표를 출력하지 않아야 하기 때문에 예외처리를 해주어야 한다.
• 먼저 x와 y좌표를 구하기 위해 두 연립방적식을 이용하여 x,y를 구해주는 함수를 정의한다.
• 이전 선분교차 2에서 교차된다고 판단되는 부분에서 만약 기울기가 같을 때 한 점에서 겹치기 위해서는 A,B의 최솟값이 C,D의 최댓값과 같거나 A,B의 최댓값이 C,D의 최솟값과 같은 경우가 되게 된다. 만약 기울기가 같지만 위의 조건을 만족하지 못할 경우 한 점에서 겹치는 것이 아니기 때문에 이 때는 좌표를 출력하지 않고 한 점에서 겹칠 때에만 겹치는 좌표를 출력해준다.

---

💻 코드

import sys
input = sys.stdin.readline
INF = 1e10

def ccw(X,Y,Z) :
    re = (X[0]*Y[1]+Y[0]*Z[1]+Z[0]*X[1])-(X[1]*Y[0]+Y[1]*Z[0]+Z[1]*X[0])
    return re

def get_intersection(A,B,C,D) :
    denominator = (B[0] - A[0]) * (D[1] - C[1]) - (B[1] - A[1])*(D[0] - C[0])
    if denominator == 0 :
        return None
    
    dx = (A[0]*B[1] - A[1]*B[0])
    dy = (C[0]*D[1] - C[1]*D[0])
    x = ((dx * (D[0] - C[0])) - (dy * (B[0] - A[0]))) / denominator
    y = ((dx * (D[1] - C[1])) - (dy * (B[1] - A[1]))) / denominator
    return (-x,-y)

x1, y1, x2, y2 = map(int,input().split())
x3, y3, x4, y4 = map(int,input().split())
A, B, C, D = (x1, y1), (x2, y2), (x3, y3), (x4, y4)

if A > B :
    A, B = B, A
if C > D :
    C, D = D, C

if ccw(A, B, C)*ccw(A, B, D) <= 0 and ccw(C,D,A)*ccw(C,D,B) <= 0 :
    if ccw(A,B,C)*ccw(A,B,D) == 0 and ccw(C,D,A)*ccw(C,D,B)== 0 :
        if A <= D and C <= B :
            print(1)
            if (x4 - x3)*(y2-y1) == (x2-x1)*(y4-y3) :   #기울기가 같을 때
                if max(x1,x2) == min(x3,x4) or max(x3,x4) == min(x1,x2) :   #한 점에서 만날 때
                    if A in [C,D] :
                        print(*A)
                    elif B in [C,D] :
                        print(*B)
            else :
                point = get_intersection(A,B,C,D)
                print(point[0], point[1])
            
        else :
            print(0)
    else :
        print(1)
        point = get_intersection(A,B,C,D)
        if point :
            print(f"{point[0]} {point[1]}")
else :
    print(0)

---