[백준 17387번] 선분 교차 2 (Python3)

import sys
input = sys.stdin.readline

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

def eq1(x,y):
  return (x2-x1)*(y-y1)-(y2-y1)*(x-x1)

def eq2(x,y):
  return (x4-x3)*(y-y3)-(y4-y3)*(x-x3)


def check():
  if eq1(x3,y3)*eq1(x4,y4) <= 0 and eq2(x1,y1)*eq2(x2,y2) <= 0:
    if x2-x1 == x4-x3 == 0:
      if max(y1,y2)>=min(y3,y4) and max(y3,y4)>=min(y1,y2):
        return 1
    elif (y4-y3)*(x2-x1) == (y2-y1)*(x4-x3):
      if y1-(y2-y1)/(x2-x1)*x1 == y3-(y4-y3)/(x4-x3)*x3:
        if max(x1,x2)>=min(x3,x4) and max(x3,x4)>=min(x1,x2):
          return 1
    else:
      return 1
  return 0

print(check())

이번 문제는 조금 더 까다로웠다.

처음 문제를 봤을때는 "뭐야 선분교차 1에서 부등호를 작거나같다로 바꿔주면 되는거 아니야?" 라고 단순하게 생각했는데, 테스트케이스에서 틀린답이 나왔다.

그래서 뭐가 문제지? 했더니 함정은 직선의 기울기가 같을때에 있었다. 두 직선이 일직선상에 있으면 무조건 부등식이 0이 나오기 때문에 '같다' 가 교차 하는지와 관계없이 무조건 성립해버리는 것이었다.

 

따라서 이에 대한 예외를 적용해주었다. 기울기가 같을 경우 직선의 방정식이 같은지를 따져보고, 직선의 방정식이 같다면 겹치는지를 따져준다.

 

그 외에 특별히 어려울 것은 없다.

 

그런데 이 문제의 난이도 기여를 보니 CCW라는 알고리즘을 사용하라고 낸 문제라고 한다. 이번 문제는 쉽게 풀었지만 CCW 개념을 나중에 쓸지도 모르니 이에 대해서 한번 알아봐야겠다.

 

 

오늘의 교훈) CCW에 대해서 알아보자