Vertices of the Hull

Difficulty: 1800 6000 ms 128 MB

geometry

Print the number of points that are VERTICES of the convex hull of the given point set (points strictly inside or on an edge do not count).

Input: the first line has N; the next N lines have distinct points x y.

Output: the number of hull vertices.

Constraints:

• 1 ≤ N ≤ 10⁵
• |coordinates| ≤ 10⁶

Sample Tests

4
0 0
2 0
2 2
0 2

4

3
0 0
1 1
2 2

2

Read the Editorial