백준 17386. 선분 교차 1

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

17386번: 선분 교차 1

 

CCW 알고리즘을 이용.

이번에는  두 선분의 시작점과 끝점이 주어진다.

선분1이 AB고 선분2가 CD 라고 하면 

CCW로 ABC의 방향을 구하고, ABD의 방향을 구한다. 

두 방향이 서로 다르다면 교차한다. 

 

하나의 선분 입장에서 다른 선분이 교차한다는 것은 다른 선분의 한쪽 끝점은 좌측에, 한쪽 끝점은 우측에 있다는 것이다.

예를들어 선분 AB기준으로 C가 좌측(반시계 방향)에 있고, D는 우측(시계 방향)에 있다면 AB와 CD가 교차한다.

 

그런데 주어지는 두번째 예제처럼 CCW(A,B,C)와 CCW(A,B,D)의 방향이 서로 달라도 교차하지 않을수 있다.

따라서 CCW(D,C,A)와 CCW(D,C,B)도 서로 방향이 다른지 판단해야 하고, 

두 경우 모두 서로 방향이 달라야 교차한다. 

 

세점이 평행한 경우는 없다고 주어지므로 CCW의 결과가 0이 될 수 는 없다. 

 

예제1

예제2