20151번 - 선분 교차 5

문제

2차원 좌표 평면 위의 선분 N개가 주어졌을 때, 교차하는 두 선분이 존재하는지 아닌지 구해보자. 한 선분의 끝 점이 다른 선분 위에 있는 것도 교차하는 것이다. 두 선분이 끝 점에서 만나는 것은 교차하는 것이 아니다.

입력

첫째 줄에 선분의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 선분의 양 끝 점 (x₁, y₁), (x₂, y₂)를 의미하는 네 정수 x₁, y₁, x₂, y₂가 주어진다.

출력

교차하는 두 선분이 존재하면 1, 아니면 0을 출력한다.

제한

• 1 ≤ N ≤ 200,000
• -10⁹ ≤ x_i, y_i ≤ 10⁹
• x_i, y_i는 정수
• 선분의 길이는 0보다 크다.

힌트