Ideal Route
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Planning an ideal hiking route is not an easy task. For this, Zenik has a detailed map of the Ukrainian Carpathians. The map marks \(n\) mountains. The coordinates of the \(i\)-th mountain are \((x_i, y_i)\).
The route can be represented as a polygon on the map. Travelers start their journey at some vertex of this polygon and walk along its sides in clockwise order.
Not every route is ideal. For Zenik, the criteria for an ideal route are as follows:
All sides of the polygon are parallel to the coordinate axes, and it does not contain self-intersections.
All mountains marked on his map lie inside or on the boundary of the polygon.
There are no two consecutive left turns on the route.
Marichka’s requirements are somewhat different. Her only condition is that all turns on the route must happen precisely at the mountains marked on the map, and not somewhere in the middle of the forest. Turns outside of known mountains, Marichka calls horrible turns.
Unfortunately, satisfying the demands of both travelers is not always possible. Therefore, Zenik wants to plan the route so that it satisfies all his criteria and contains as few horrible turns as possible.
Help Zenik find out what the minimum number of horrible turns the route can contain.
Input
The first line contains a single integer \(n\) — the number of mountains marked on Zenik’s map.
The next \(n\) lines each contain two integers \(x_i\), \(y_i\) — the coordinates of the mountains. All mountain coordinates are distinct.
Output
In a single line, output a single integer — the minimum number of horrible turns in a route that satisfies Zenik’s criteria.
Constraints
\(1 \le n \le 10^{5}\),
\(-10^{9} \le x_i, y_i \le 10^{9}\),
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 0 0 1 0 0 1 | 1 |
| Input (stdin) | Output (stdout) |
|---|---|
| 5 0 0 -1 0 1 0 0 -1 0 1 | 3 |
Notes
Route for the first example:
Example of a route with three horrible turns for the second example:
Example of a route that does not satisfy Zenik’s criteria, because it contains two consecutive left turns when moving along it in clockwise order:
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|