405092: GYM101790 B Forest protection
Description
To protect the forest from poachers, it was decided to surround all the trees with barbed wire.
When purchasing materials for the fence, an error was made, and now you have an unlimited supply of wire and only one pillar.
Barbed wire can be stretched between two trees or a tree and a pillar only in a straight line. If a tree touches a barbed wire, its bark is damaged.
Determine the minimum number of trees have to be damaged provided that all trees must be inside closed barbed wire fence, and the pillar can be placed in any free point of the plane.
InputThe first line contains one integer N (3 ≤ N ≤ 105).
The folling N lines contains two integers Xi, Yi, denoting coordinates of i-th tree ( - 106 ≤ Xi, Yi ≤ 106). Each tree has unique coordinates.
OutputDisplay the minimum number of trees with damaged bark.
ExamplesInput3Output
0 0
4 2
2 1
3Input
5Output
0 1
-5 -2
4 0
2 -2
4 -4
2Note
The one of possible solutions for the second sample is shown below (damaged trees are marked as crosses, the pillar is a circle, barbed wire is a dashed line):