Submit solution

Points: 1
Time limit: 2.0s
Memory limit: 256M

Problem types

Deren and Aslı are planning a subway trip in Ankara, so that they can take beautiful photographs. Deren selects \(\mathbf{N}\) distinct stations \(S_1, S_2, \ldots, S_\mathbf{N}\) he would like to visit in the given order. Then Aslı tries to draw a travel plan on the map. The plan should be a polygonal chain that passes through Deren's stations in the provided order.

Formally, a subway station is a point on a 2D plane and a travel plan is a sequence of directed line segments such that each next one starts where the previous ends. The first line segment can start and the last one can end anywhere. If you follow the plan from the beginning to the end you should visit stations \(S_1, S_2, \ldots, S_\mathbf{N}\) in that order. However, in between the chain can cross other listed stations (already visited or not). Besides, a travel plan can cross or overlap itself. For example, after visiting \(S_2\) and before visiting \(S_3\) the plan can pass through \(S_1\) or \(S_5\). And \(S_5\) will be visited only when the plan crosses it after visiting \(S_4\).

Aslı would like to build a travel plan with the minimal possible number of segments. Can you give him a hand?

Note that every time you change a direction (even to exact opposite direction), you start a new trip segment. You can change direction at any point, not necessarily on metro stations.


The first line contains the number of stations \(\mathbf{N}\) selected by Deren. The following \(\mathbf{N}\) lines describe the stations. The \(i\)-th line contains two integers \(\mathbf{x}_i\) and \(\mathbf{y}_i\) which are coordinates of station \(S_i\).

  • \(2 \le \mathbf{N} \le 10^6\),
  • \(-10^9 \le \mathbf{x}_i, \mathbf{y}_i \le 10^9\),

All station locations are dictinct.


The minimal number of travel plan segments.



0 0
1 1
2 0
2 -1
4 0




One possible travel plan would be starting at the point (0, 0). Going to the points (2, 2), (2, -1) and (4, 0) in that order. This way, you would follow all the stations in order and would complete the plan with 3 line segments.