선분 교차 1 (17386번) - 백준 (BOJ)

https://www.acmicpc.net/problem/17386

17386번: 선분 교차 1

 

 

백준 - 선분 교차 1 (17386번)

 

난이도 : Gold 3

알고리즘&자료구조 : Geometry (기하학)

---

★ 핵심 Idea ★

 

◎ 선분 1을 포함하는 직선의 방정식을 A, 선분 2를 포함하는 직선의 방정식을 B라고 설정한다.

 

두 선분 1, 2가 교차하려면,

아래의 두 가지 경우를 동시에 만족해야 한다.

 

① 직선 B로 인해 나눠지는 평면 B1과 B2가 있다고 하면, 선분 1의 양 끝 점이 서로 다른 평면에 위치해야 한다.

② 직선 A로 인해 나눠지는 평면 A1과 A2가 있다고 하면, 선분 2의 양 끝 점이 서로 다른 평면에 위치해야 한다.

 

위의 조건을 코드로 구현하면 된다.

주의할 점은, 두 선분 중 하나라도 y축에 평행하는 경우 예외 처리가 필요하다.

 

 

< 전체 코드 >

 

def make_line(x1, y1, x2, y2):
    def line(x):
        return (y2-y1) / (x2-x1) * (x-x1) + y1

    if x1 == x2:
        return 'v'
    return line


def main():
    x11, y11, x12, y12 = map(int, input().split())
    x21, y21, x22, y22 = map(int, input().split())
    (x11, y11, x12, y12) =  (x11, y11, x12, y12) if x11 <= x12 else (x12, y12, x11, y11)
    (x21, y21, x22, y22) =  (x21, y21, x22, y22) if x21 <= x22 else (x22, y22, x21, y21)
    (x11, y11, x12, y12, x21, y21, x22, y22) =\
        (x21, y21, x22, y22, x11, y11, x12, y12) if x11 == x12 else (x11, y11, x12, y12, x21, y21, x22, y22)
    line_1 = make_line(x11, y11, x12, y12)
    line_2 = make_line(x21, y21, x22, y22)
    
    if line_1 == 'v' or (y21 - line_1(x21)) * (y22 - line_1(x22)) > 0:
        print(0)
    elif line_2 == 'v':
        print(1 if x11 < x21 < x12 else 0)
    elif (y11 - line_2(x11)) * (y12 - line_2(x12)) > 0:
        print(0)
    else:
        print(1)


if __name__ == '__main__':
    main()