[백준 파이썬] 17387 선분 교차 2

📌문제 출처

백준 단계별 문제풀이 : 기하2
https://www.acmicpc.net/problem/17387

17387번: 선분 교차 2

❓ 문제

📗 풀이 코드

'''
선분 교차1의 문제에 한 선분의 끝 점이 다른 선분 위에 있는 경우도 교차하는 것으로 포함하는 문제이다.
일직선에 놓인 세 점의 외적은 0이므로 이 조건을 추가해주자.
이때 두 선분이 일직선 위에 있는 경우에는 모두 외적이 0이지만 겹치지 않는 경우도 있다.
기준 선분을 바꿔도 외적 벡터 쌍의 곱이 모두 0인 경우에 일직선이기에 이 경우를 추가 확인하자.
'''
input = open(0).readline

def solution():
    xs,ys = [],[] # 모든 점의 x좌표와 y좌표
    for _ in range(2):
        x1,y1,x2,y2 = map(int, input().split())
        xs += [x1,x2]
        ys += [y1,y2]

    def ccw(xs,ys): # 세 점의 x좌표와 y좌표
        res = 0
        for i in range(3):
            res += xs[i]*ys[(i+1)%3] - xs[(i+1)%3]*ys[i]
        return res
    
    # 기준 선분을 바꿔가며 교차 확인
    res1 = ccw(xs[:2]+[xs[2]],ys[:2]+[ys[2]])*ccw(xs[:2]+[xs[3]],ys[:2]+[ys[3]])
    res2 = ccw(xs[2:]+[xs[0]],ys[2:]+[ys[0]])*ccw(xs[2:]+[xs[1]],ys[2:]+[ys[1]])

    if res1<=0 and res2<=0 : # 교차하거나 세 점 이상이 일직선
        if res1 == res2 == 0 : # 네 점이 일직선인 경우
            x_min1, y_min1, x_max1, y_max1 = min(xs[:2]), min(ys[:2]), max(xs[:2]), max(ys[:2])
            x_min2, y_min2, x_max2, y_max2 = min(xs[2:]), min(ys[2:]), max(xs[2:]), max(ys[2:])
            # 겹치는 경우 찾기
            if x_min1 <= x_max2 and x_min2 <= x_max1 and y_min1 <= y_max2 and y_min2 <= y_max1 :
                return 1
            return 0
        return 1 # 교차하거나 세 점이 일직선
    return 0 # 교차하지 않는 경우

if __name__ == '__main__':
    print(solution())