403661: GYM101234 H Split Game

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. Also, the actual lower bound on N is 3.

• 1 ≤ N ≤ 10⁵
• 1 ≤ x_i, y_i ≤ 10⁹
• if i ≠ j, then (x_i, y_i) ≠ (x_j, y_j)
• the vertices are given in counter-clockwise order
• the polygon is simple: its sides have no common points except the vertices

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.

4
1 1
2 1
2 2
1 2

2

6
2 1
4 2
8 4
4 8
2 4
1 2

2

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

5