만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

선분 교차 4

시간 제한1초메모리 제한512 MB

요약

정수 좌표를 가진 N개의 선분이 주어질 때, 끝점이 닿거나 다른 선분 위에 놓이는 경우를 포함하여 두 선분이 교차하는지 판별합니다.

난이도: 보통10점 중 7점
유형: 기하, 정렬, 트리
정답자: 아직 제출이 없습니다

문제

2차원 좌표 평면 위에 선분 N개가 주어진다. 교차하는 두 선분이 있는지 구하라. 한 선분의 끝 점이 다른 선분이나 끝 점 위에 있어도 교차하는 것으로 본다.

입력

첫째 줄에 선분의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 선분의 양 끝 점 $(x_1, y_1)$ , $(x_2, y_2)$ 를 나타내는 네 정수 $x_1, y_1, x_2, y_2$ 가 주어진다.

출력

교차하는 두 선분이 있으면 1, 없으면 0을 출력한다.

제한

1 ≤ N ≤ 200,000
$-10^9 \le x_i, y_i \le 10^9$
$x_i$ , $y_i$ 는 정수이다.
선분의 길이는 0보다 크다.

예제5

예제 1
입력
```
2
1 1 5 5
1 5 5 1
```
예상 출력
```
1
```
예제 2
입력
```
2
1 1 5 5
6 10 10 6
```
예상 출력
```
0
```
예제 3
입력
```
3
1 1 2 2
3 3 4 4
5 5 6 6
```
예상 출력
```
0
```
예제 4
입력
```
3
1 1 3 3
3 3 5 5
5 5 6 6
```
예상 출력
```
1
```
예제 5
입력
```
4
1 1 5 5
3 3 1 3
6 10 10 6
5 6 2 4
```
예상 출력
```
1
```

Loading...