백준 17387번 선분 교차 2

네 점을 A, B, C, D라고 하고 선분 AB와 CD의 교차를 확인한다고 하자.

그럼 우선 두 점 중 같은 게 있는지를 확인해주어야 한다.(코드에서는 sp 함수)

같은 게 있으면 1을 출력하고 리턴해준다.

그리고 나서 한 점이 다른 선분 위에 있는지를 확인해준다. (코드에서는 ep함수)

확인하는 방법은, 우선 한 점이 다른 선분과 일직선상에 있는지를 확인해주어야 하는데 이는 외적을 통해서 할 수 있다. 그리고 선분 위에 있는지는 내적해서 부호가 음수여야 선분 위에 존재하므로 이를 이용해준다.

(코드에서 외적 함수는 op, 내적 함수는 ip) 그래서 ep가 true면 1을 출력하고 return해준다.

만약 여기까지도 해당이 안되면, 이제 각 점이 다른 선분을 기준으로 서로 반대편에 위치해야한다는 것이 교차하기 위한 동치조건이 된다. 어느 편에 있는지는 외적을 통해 확인할 수 있다. 외적 값의 부호가 서로 반대여야 서로 반대편에 있게 된다.