소 장애물 경주 II

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

요약

선분 N개 중 하나를 제거했을 때 나머지 선분들이 서로 교차하지 않게 되는 선분의 가장 작은 번호를 구합니다.

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

문제

옛날에 Farmer John은 여러 가지 새로운 소 스포츠를 구상했다. 그중 하나가 Cow Steeplechase로, 소 떼가 코스를 달리며 장애물을 뛰어넘는 경기다. 이 종목에 관심을 끌려던 과거의 노력은 성과가 엇갈렸다. 그래서 그는 종목을 더 널리 알리려고 농장에 더 큰 Cow Steeplechase 코스를 만들고 있다.

새 코스는 $1$ 부터 $N$ 까지 번호가 붙은 $N$ 개의 장애물을 중심으로 설계되었다. 단, $2 ≤ N ≤ 10^5$ 이다. 각 장애물은 코스의 2차원 지도 위에 있는 선분이다. 어떤 두 선분도 끝점에서 만나는 경우를 포함해 교차해서는 안 된다.

Farmer John이 지도를 그리다가 실수를 해서 일부 선분이 서로 교차한다. 하지만 선분 하나만 지우면 어떤 선분도 교차하지 않는, 원래 의도한 지도로 돌아간다. 지우면 나머지 선분들이 교차하지 않게 되는 선분을 찾아라. 그런 선분이 여럿이면 입력에서 번호가 가장 작은 것을 출력한다.

입력

첫 줄에 $N$ 이 주어진다. 이어지는 $N$ 개의 줄에는 각각 정수 네 개 $x_1$ $y_1$ $x_2$ $y_2$ 로 선분 하나가 주어진다. 선분의 양 끝점은 $(x_1, y_1)$ 과 $(x_2, y_2)$ 이다. 모든 정수의 절댓값은 $10^9$ 이하다. 모든 끝점은 서로 다르다.

출력

나머지 선분들이 서로 교차하지 않게 되는 선분의 입력 번호 중 가장 작은 것을 출력한다.

힌트

좌표 값이 커서 계산할 때 정수 오버플로에 주의해야 한다.

예제1

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