A hydrology team records the water level of a reservoir on a set of distinct days, and wants to draw the simplest possible chart of level versus day. Given the recorded (day, level) readings — not necessarily listed in day order — plot them in order of increasing day and connect each consecutive pair of readings with a straight line segment. Whenever several consecutive segments happen to lie along the very same straight line (that is, they share identical slope), the chart only needs to draw that line once instead of drawing each little segment separately.
Determine the minimum number of straight line segments the finished chart requires.
Line 1: an integer n, the number of readings. Next n lines: two space-separated integers day_i and level_i — the day and the recorded water level for the i-th reading.
Print a single integer: the minimum number of straight line segments needed to draw the level-versus-day chart through all n readings in day order.
Example 1
Input
8 1 8 2 7 3 6 4 5 5 5 6 4 7 3 8 2
Expected
3
Explanation
Sorted by day the readings are (1,8),(2,7),(3,6),(4,5),(5,5),(6,4),(7,3),(8,2). From day 1 through day 4 the level drops by 1 each day (slope -1), so those three segments lie on one line. From day 4 to day 5 the level stays at 5 (slope 0) — a different line. From day 5 through day 8 the level drops by 1 per day again (slope -1), but since this run isn't adjacent to the first slope -1 run it forms its own, third line. That gives exactly 3 distinct lines.
Example 2
Input
4 3 6 1 2 4 8 2 4
Expected
1
Explanation
The readings, given out of day order, are (3,6),(1,2),(4,8),(2,4). Sorted by day they become (1,2),(2,4),(3,6),(4,8), and every consecutive pair rises by exactly 2 levels per day, so all three connecting segments share one slope and the whole chart is drawn with a single straight line.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →