In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
We have a cartesian coordinate system drawn on a sheet of paper. Let us consider broken lines that can be drawn with a single pencil stroke from the left to the right side of the sheet. We also require that for each segment of the line the angle between the straight line containing this segment and the axis belongs to range. A broken line fulfilling above conditions is called a flat broken line.
Suppose we are given distinct points with integer coordinates. What is the minimal number of flat broken lines that should be drawn in order to cover all the points (a point is covered by a line if it belongs to this line)?
For points whose coordinates are , , , , , the minimal number of flat broken lines covering them is .
Write a program that:
In the first line of the standard input there is one positive integer , not greater than , which denotes the number of points. In the following lines there are coordinates of points. Each line contains two integers separated by a single space, . The numbers in the -st line, , are the coordinates of the -th point.
Your program should write exactly one integer in the first and only line of the standard output. The number should be a minimal number of flat broken lines that should be drawn in order to cover all the points.
For the input data:
6 1 6 10 8 1 5 2 20 4 4 6 2
the correct result is:
3
Task author: Krzysztof Sobusiak.