Detour Buster#3051
The Green Parcel Services company employs cyclists to deliver parcels across a large metropolitan city, and employees are paid according to the distances they must travel to deliver parcels. Each company bicycle is equipped with a global positioning system that records its position every few seconds. The sequence of positions for one delivery is called a track, and the length of a track—defined as the sum of Euclidean distances between each pair of consecutive recorded points—is used to calculate the employee's payment.
A recent audit of the recorded tracks revealed that some tracks self-intersect, indicating that some employees make unnecessary detours. Your task is to write a program to process a given track and calculate the length of the shortest possible track from the first to the last point of the original track. The shortest possible track must be part of the original track and may include traveling in the same or opposite direction along the original track.
Input starts with an integer on a line by itself, representing the number of tracks to be shortened. The description of each track begins with a positive integer on a line by itself, representing the number of recorded points that define the track. Each of the following lines contains two integers, separated by a single space, defining the and coordinates (in metres) of a point on the track. The points are listed in their order of appearance on the track.
Any two successive points, forming a segment, will be no more than metres apart, and any segment will not intersect more than other segments. All and coordinates are between and , inclusive. is between and , inclusive.
For each input track, output a single integer on a line by itself: the length of the shortest track in metres, rounded to the nearest integer.
Reminder: Rounding a positive number R.xyz to the nearest integer:
If the first decimal digit (that is, ) is less than , the rounded value is .
Otherwise, the rounded value is R + 1.
Example 1