BaekJoon 17386번 : 선분 교차 1 (python)

📝 BaekJoon 17386번 : 선분 교차 1 (G3 36.347%)

---

🔎 선분 교차 1 문제

---

📌 아이디어

CCW알고리즘을 이용하여 두 선분이 교차하는지 확인할 수 있고, 두 선분을 직접 구해서 교차 지점을 구할 수도 있다.

---

💭 풀이

• CCW알고리즘은 "평면에 놓여진 세 점의 방향관계를 구하는 알고리즘"이다. 이전에 풀었던 문제처럼 두 벡터의 외적에 대하여 시계방향이면 음수, 반시계 방향이면 양수를 출력하는 알고리즘이다.
• 해당 알고리즘을 이용하면 A,B와 C,D점을 잇는 두 선분이 있을 때 CCW(A,B,C)와 CCW(A,B,D)의 값이 하나는 반시계, 하나는 시계 방향으로 둘의 곱이 음수가 나오거나 두 값중 0이라면 두 선분은 교차되어 있다고 판단할 수 있게 된다.
• 예외 1로 CCW(A,B,C)*CCW(A,B,D) <= 0을 만족하지만 AB와 CD가 교차가 되지 않을 수도 있다. 이 때는 CCW(C,D,A)와 CCW(C,D,B)도 위 두 조건과 똑같이 <=0이 되는지 확인을 해주어야 한다.

---

💻 코드

import sys
input = sys.stdin.readline

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

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 ccw(A, B, C)*ccw(A, B, D) <= 0 and ccw(C,D,A)*ccw(C,D,B) <= 0 :
    print(1)
else :
    print(0)

---

import sys
input = sys.stdin.readline
INF = 1e10
x1, y1, x2, y2 = map(int,input().split())
x3, y3, x4, y4 = map(int,input().split())

if x1-x2 != 0 :
    a1 = (y1-y2)/(x1-x2)
    b1 = (y1 - a1*x1)
    A, B, E = a1, -1, b1
else :
    A, B, E = 1, 0, -x1


if x3-x4 != 0 :
    a2 = (y3-y4)/(x3-x4)
    b2 = (y3 - a2*x3)
    C, D, F = a2, -1, b2
else :
    C, D, F = 1, 0, -x3

if (A*D-B*C) != 0 :
    x = (B*F-E*D)/(A*D-B*C)
    y = (E*C-A*F)/(A*D-B*C)
    if min(x1,x2)<= x <= max(x1,x2) and min(x3,x4) <= x <= max(x3,x4) and min(y1,y2) <= y <=max(y1,y2) and min(y3,y4) <= y <= max(y3,y4) :
        print(1)
    else :
        print(0)
else :
    print(0)

---