시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 4 2 2 50.000%

문제

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

입력

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

출력

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

제한

  • 1 ≤ N ≤ 200,000
  • -109 ≤ xi, yi ≤ 109

예제 입력 1

2
1 1 5 5
1 5 5 1

예제 출력 1

1

예제 입력 2

2
1 1 5 5
6 10 10 6

예제 출력 2

0

예제 입력 3

3
1 1 2 2
3 3 4 4
5 5 6 6

예제 출력 3

0

예제 입력 4

3
1 1 3 3
3 3 5 5
5 5 6 6

예제 출력 4

0

예제 입력 5

4
1 1 5 5
3 3 1 3
6 10 10 6
5 6 2 4

예제 출력 5

1

출처