Baekjoon 17386. 선분 교차 1 / Python

알고리즘 설명

문제 설명

2-D 좌표평면 위에 두 선분이 교차하는지를 확인하는 문제

코드 설명

CCW 알고리즘을 이용하여 두 선분의 교차여부를 확인한다

• CCW 알고리즘
  세 점이 주어졌을 때, 점 A에서 B를 바라 보는 방향을 기준으로 점 C가 시계방향에 있는지, 반시계방향에 있는지를 확인하는 알고리즘
  CCW(A, B, C) = (Bx - Ax) * (Cy - Ay) - (By - Ay) * (Cx - Ax)
  CCW함수의 값이
  • 양수이면 반시계방향
  • 음수이면 시계방향
  • 0이면 일직선 상에 있음을 나타냄
• 두 선분의 교차여부 확인
  두 선분 L1(A1, A2), L2(B1, B2)가 있을 때
  1. 두 선분이 일직선 상에 있어서 겹치는 경우
  2. CCW(A1, A2, B1) * CCW(A1, A2, B2) < 0 and CCW(B1, B2, A1) * CCW(B1, B2, A2) < 0 인 경우

import sys
input = sys.stdin.readline

def ccw(a1, b1, a2, b2, a3, b3):
    """세 점 (a1, b1), (a2, b2), (a3, b3)의 방향성을 판별하는 함수"""
    return (a2 - a1) * (b3 - b1) - (b2 - b1) * (a3 - a1)

def check(a, b):
    """두 선분이 교차하는지 확인하는 함수"""
    l1 = ccw(a[0], a[1], a[2], a[3], b[0], b[1]) * ccw(a[0], a[1], a[2], a[3], b[2], b[3])
    l2 = ccw(b[0], b[1], b[2], b[3], a[0], a[1]) * ccw(b[0], b[1], b[2], b[3], a[2], a[3])
    
    if l1 <= 0 and l2 <= 0:
        if l1 == 0 and l2 == 0:
            d1 = max(a[0], a[2]) >= min(b[0], b[2]) and max(b[0], b[2]) >= min(a[0], a[2])
            d2 = max(a[1], a[3]) >= min(b[1], b[3]) and max(b[1], b[3]) >= min(a[1], a[3])
            if d1 and d2:
                return 1
            return 0
        else:
            return 1
    return 0

a = tuple(map(int, input().split()))
b = tuple(map(int, input().split()))

print(check(a, b))