Split Game

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

요약

제1사분면에 있는 단순 다각형의 꼭짓점이 반시계 방향으로 주어질 때, 원점을 지나는 한 직선이 다각형을 나눌 수 있는 0이 아닌 넓이 영역의 최대 개수를 구한다.

난이도: 보통10점 중 6점
유형: 기하, 정렬, 투 포인터
정답자: 아직 제출이 없습니다

문제

Consider the following game about splitting a simple polygon with $N$ vertices on a plane. The purpose of this game is using a straight line which passes through the origin to split the given simple polygon into as many non-zero area regions as possible. Please finish the game with the best result possible.

입력

The input consists of $N+1$ lines. The first line contains an integer $N$ . The $i$ -th of the following $N$ lines consists of two integers $x\_i$ and $y\_i$ indicating the vertices of the given polygon in counter-clockwise order.

출력

Output one integer: the maximum number of non-zero area regions into which the given polygon can be split by a single line passing through the origin.

제한

$1 \le N \le 10^5$
$1 \le x\_i, y\_i \le 10^9$
if $i \ne j$ , then $(x\_i, y\_i) \ne (x\_j, y\_j)$
the vertices are given in counter-clockwise order

힌트

예제3

예제 1
입력
```
4
1 1
2 1
2 2
1 2
```
예상 출력
```
2
```
예제 2
입력
```
6
2 1
4 2
8 4
4 8
2 4
1 2
```
예상 출력
```
2
```

예제 3

입력

예상 출력