[BOJ 17386] 선분 교차 1

문제

---

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

풀이

---

세 점이 일직선 위에 있는 경우가 없으므로 매우 간단하다.

반 년 전에 맨 처음 풀 땐, 한 선분을 연장해 만든 직선을 기준으로 나눠진 두 영역에서 나머지 선분의 끝 점이 어디에 속해있는지를 통해 교차 여부를 판단했었다.

하지만 CCW를 이용하니 풀이가 한결 간결해졌다.

두 선분을 $ \overline{AB}, \overline{CD} $라고 하면, 두 선분이 교차하기 위해서 CCW(A, B, C)와 CCW(A, B, D)의 부호가 달라야 하고, CCW(C, D, A)와 CCW(C, D, B)의 부호가 달라야 한다.

코드

---

import sys

x1, y1, x2, y2 = map(int, sys.stdin.readline().split())
x3, y3, x4, y4 = map(int, sys.stdin.readline().split())


def ccw(x1, y1, x2, y2, x3, y3):
    return (x2 - x1) * (y3 - y2) - (x3 - x2) * (y2 - y1)


print(int((ccw(x1, y1, x2, y2, x3, y3) * ccw(x1, y1, x2, y2, x4, y4) < 0) and (ccw(x3, y3, x4, y4, x1, y1) * ccw(x3, y3, x4, y4, x2, y2) < 0)))