Baekjoon 17387. 선분 교차 2 / Python

CW (Counter ClockWise) 정의

CCW를 사용하여 세 점의 방향성을 다음과 같이 정의할 수 있습니다:

• 점이 시계 방향으로 돌면 음수 값을 가집니다.
• 점이 반시계 방향으로 돌면 양수 값을 가집니다.
• 세 점이 일직선 상에 있으면 0을 가집니다.

CCW를 계산하는 수식은 다음과 같습니다: ccw(a,b,c)=(b.x−a.x)⋅(c.y−a.y)−(b.y−a.y)⋅(c.x−a.x)\text{ccw}(a, b, c) = (b.x - a.x) \cdot (c.y - a.y) - (b.y - a.y) \cdot (c.x - a.x)ccw(a,b,c)=(b.x−a.x)⋅(c.y−a.y)−(b.y−a.y)⋅(c.x−a.x)

선분 교차 판정

두 선분이 교차하는지 판정하는 방법은 다음과 같습니다:

1. 선분 (a1, a2)와 (b1, b2)의 CCW 값을 계산합니다.
2. 선분 (b1, b2)와 (a1, a2)의 CCW 값을 계산합니다.
3. 두 선분이 교차하려면 다음 조건을 만족해야 합니다:
   • 각 선분의 끝점이 다른 선분의 양 끝점을 기준으로 서로 반대쪽에 있어야 합니다.
   • 세 점이 일직선 상에 있는 경우, 두 선분이 서로 겹쳐 있어야 합니다.

def ccw(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 (min(a[0], a[2]) <= max(b[0], b[2]) and max(a[0], a[2]) >= min(b[0], b[2]) and
            min(a[1], a[3]) <= max(b[1], b[3]) and max(a[1], a[3]) >= min(b[1], b[3])):
            return 1
        else:
            return 0
    return 1 if l1 <= 0 and l2 <= 0 else 0


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

print(check(a, b))