문제 보기
union-find와 ccw의 향연입니다.
자주 볼 수 없는 조합이군요.

선분 교차에도 ccw를 이용할 수 있습니다.
한 선분의 양 끝 점에 대해서 다른 선분의 두 끝점에 대해 ccw를 하고,
그 반대로도 해주면 선분 교차 여부를 확인할 수 있답니다.
자세한 내용은 그림만 살짝 그려보아도 알 수 있습니다.

그러면, 이 문제에서 주의할 점이 무엇일까요?
선분 교차 판별 과정에서의 예외처리가 가장 실수가 잦은 곳입니다.
두 선분이 한 직선 위에 존재하는 경우를 처리하는 것이 관건인데
사실 저도 거기서 틀렸습니다.

구현

그래서 저렇게 고쳤습니다.
교차 판별하는 코드는 외워야 한답니다. (너는?)