Drone Waypoints Navigation

Drone Waypoints Navigation

A drone is tasked with traversing a series of waypoints while staying within its battery capacity. Given a maximum battery capacity \(V\) and a sequence of \(N\) waypoints, the drone starts at the first waypoint and attempts to move sequentially from one waypoint to the next. The distance between two consecutive waypoints \((x_1, y_1)\) and \((x_2, y_2)\) is calculated using the Euclidean distance formula:

\(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\)

The drone can complete a segment if the cumulative distance traveled remains less than or equal to \(V\). Your task is to determine the maximum number of segments (transitions between waypoints) the drone can traverse before its battery is exhausted.

inputFormat

The input begins with an integer \(T\) indicating the number of test cases. Each test case starts with two space-separated integers \(V\) and \(N\), where \(V\) is the maximum battery capacity and \(N\) is the number of waypoints. This is followed by \(N\) lines, each containing two space-separated integers representing the \(x\) and \(y\) coordinates of a waypoint.

outputFormat

For each test case, output a single integer on a new line representing the maximum number of consecutive segments (i.e. transitions between waypoints) the drone can travel without exceeding its battery capacity.

1
25 4
0 0
3 4
3 0
0 0

3