403661: GYM101234 H Split Game

Memory Limit:0 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

H. Split Gametime limit per test1 secondmemory limit per test512 mebibytesinputstandard inputoutputstandard output

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.

Input

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 xi and yi indicating the vertices of the given polygon in counter-clockwise order. Also, the actual lower bound on N is 3.

  • 1 ≤ N ≤ 105
  • 1 ≤ xi, yi ≤ 109
  • if i ≠ j, then (xi, yi) ≠ (xj, yj)
  • the vertices are given in counter-clockwise order
  • the polygon is simple: its sides have no common points except the vertices
Output

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.

ExamplesInput
4
1 1
2 1
2 2
1 2
Output
2
Input
6
2 1
4 2
8 4
4 8
2 4
1 2
Output
2
Input
10
1 1
3 1
3 3
5 3
5 5
4 5
4 4
2 4
2 2
1 2
Output
5
Note

加入题单

上一题 下一题 算法标签: