P5939 [POI 1998 R3] Polyline

A 2D Cartesian coordinate system is given. We require that a polyline can be drawn in one stroke only from left to right, and the angle between each segment of the polyline and the $x$-axis is in $[-45^\circ, 45^\circ]$. A polyline that satisfies the above requirements is called a straight polyline. Given $n$ lattice points on the coordinate plane, what is the minimum number of straight polylines needed to cover all the points?

The first line contains a positive integer $n$, representing the number of points. The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th point.

Output a single integer, representing the minimum number of straight polylines required.

For $100\%$ of the testdata, $1 \le n \le 30000$, $0 \le x_i, y_i \le 30000$. Translated by ChatGPT 5