17386 선분 교차 1

17386번: 선분 교차 1

첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다.

www.acmicpc.net

CCW를 안쓰고 풀 수 있고, 나는 안쓰고 풀었다 일단

근데 그 과정이 굉장히 힘들고 험난하다

그리고 결론적으로 다음 문제인 17387 선분 교차 2를 풀기 굉장히 어려울 것이다

지랄말고 CCW로 풀자

방법론

- 한 선분 AB, 다른 선분 CD 가 있다고 하자

- ABC에 대해서 CCW를 돌리고, ABD에 대해서 CCW를 돌려서 그 결과값을 곱한 값이 음수라면, 선분 AB를 연장한 직선이 좌표평면을 두 구간으로 분할 할 때, C와 D는 각각 다른 영역에 있다는 것이다.

- CDA에 대해서 CCW를 돌리고, CDB에 대해서 CCW를 돌려서 또 그걸 곱한 값이 음수면, 선분 CD를 연장한 직선이 좌표평면을 두 구간을 분할 할 때, A와 B는 각각 다른 영역에 있다는 것이다.

- 두 선분이 교차했다는건, 아무튼 CCW( A B C) * CCW (A B D) < 0 , CCW (C D A) * CCW (C D B) < 0 를 동시에 만족한다는 뜻이다. ( 이 문제 한정해서 0 미만이다. 다음 문제에서는 여러 조건이 더 추가된다. )

김심야 팬