선분 교차 판별

문제

2차원 좌표 평면 위에 두 선분이 주어진다. 두 선분이 교차하는지 판별하라. 여기서 교차란 한 선분의 한 점 이상이 다른 선분 위에 위치하는 경우를 뜻한다. 따라서 두 선분이 끝점에서만 만나는 경우나 아예 일치하는 경우, 혹은 한 선분이 다른 선분의 일부를 포함하는 경우도 모두 교차로 판별한다.

이 문제는 세 점의 방향 관계를 판별하는 CCW(Counter-Clockwise) 알고리즘을 사용하여 해결할 수 있다.

입력

첫째 줄에 선분 1의 양 끝점 좌표 x1, y1, x2, y2가 공백으로 구분되어 주어진다.
둘째 줄에 선분 2의 양 끝점 좌표 x3, y3, x4, y4가 공백으로 구분되어 주어진다.

제한

• -1,000,000 ≤ 모든 좌표(x1, y1, x2, y2, x3, y3, x4, y4) ≤ 1,000,000
• 모든 좌표는 정수이다.

출력

두 선분이 교차하면 YES, 교차하지 않으면 NO를 출력한다.

입출력 예시

입력 1

1 1 5 5
1 5 5 1

출력 1

YES

입력 2

0 0 1 0
2 0 3 0

출력 2

NO

설명: 각 예시는 문제의 규칙에 따라 입력을 처리했을 때의 출력이다.