Jungle Outpost

Time limit1sMemory limit128 MB

Summary

Given the vertices of a convex polygon in order, find the placement inside it maximizing the minimum number of vertices whose removal destroys coverage, essentially finding the minimum piercing/hitting number related to diagonal crossing structure.

Level: Medium7 of 10
Topics: Geometry, Binary search, Greedy
Solved: No attempts yet

Problem

There is a military base hidden deep in the jungle. It is surrounded by $n$ watchtowers equipped with ultrasonic generators. In this problem each watchtower is a point on the plane.

The watchtowers generate an ultrasonic field that protects every object lying strictly inside the convex hull of the towers. No tower lies strictly inside the convex hull, and no three towers are collinear.

The enemy can destroy some of the towers. When that happens, the protected area shrinks to the convex hull of the remaining towers.

The base commander wants to build the headquarters somewhere inside the protected area. To make it as safe as possible, he wants to maximize the number of towers the enemy must destroy in order to leave the headquarters unprotected.

Input

The first line contains a single integer $n$ ( $3 \le n \le 50\,000$ ) — the number of watchtowers. Each of the next $n$ lines contains two integers, the Cartesian coordinates of one tower. Every coordinate does not exceed $10^6$ in absolute value. The towers are listed in the order in which their convex hull is traversed clockwise.

Output

Print a single integer: the number of watchtowers the enemy must destroy to leave the headquarters unprotected, assuming the headquarters is placed optimally.

Examples5

Example 1
Input
```
3
0 0
50 50
60 10
```
Expected output
```
1
```
Example 2
Input
```
5
0 0
0 10
10 20
20 10
25 0
```
Expected output
```
2
```
Example 3
Input
```
3
0 5
4 -1
-3 -3
```
Expected output
```
1
```
Example 4
Input
```
4
10 9
8 1
0 0
-2 7
```
Expected output
```
1
```

Example 5

Input

Expected output