Reconstruct Dancing Line

This problem is based on the famous game Dancing Line. In the game, the route is a broken line formed by a sequence of points. Every time you click, the line rotates exactly by \(90^\circ\) either clockwise or anticlockwise, and the rotation directions of any two successive turns are different.

You are given the coordinates (with integer \(x\) and \(y\) values) of the starting point, the ending point, and all the turning points; however, the points are provided in a random order. Your task is to reconstruct the original route (i.e. determine the order of points) that meets the following conditions:

• If the restored route is \(P_0,P_1,\dots,P_n\) (with \(P_0\) as the start and \(P_n\) as the end), then for every segment \(\overrightarrow{P_{i-1}P_i}\) (for \(1 \le i \le n\)), the following holds:
• For every triple \(P_{i-2},P_{i-1},P_i\) with \(i \ge 2\), the angle between \(\overrightarrow{P_{i-2}P_{i-1}}\) and \(\overrightarrow{P_{i-1}P_i}\) is exactly \(90^\circ\) (i.e. their dot product is zero).
• For any two consecutive turns (i.e. at \(P_{1},P_{2},\dots,P_{n-1}\); note that the starting and ending points are not turning points), the rotation directions alternate. In other words, if the turn at \(P_{i}\) is clockwise then the turn at \(P_{i+1}\) must be anticlockwise, and vice versa. (The turn direction at a point \(P_{i}\) can be determined by the sign of the cross product \((P_{i}-P_{i-1}) \times (P_{i+1}-P_{i})\).)

After restoring the route, its difficulty is evaluated by the value \(s\) defined as follows:

\[ s=\sum_{i=1}^{n}\left(\frac{d(P_{i-1},P_i)}{v}\right)^2, \]

where:

• \(d(A,B)\) is the Euclidean distance between points \(A\) and \(B\).
• \(v\) is a given positive integer representing the speed of the line.

Your goal is to restore the correct order of points and compute \(s\).

inputFormat

The input consists of:

 v n
 x1 y1
 x2 y2
 ...
 xn yn

where:

• \(v\) is a positive integer (the speed of the line).
• \(n\) is the total number of points (including the start, end, and all turning points).
• Each of the following \(n\) lines contains two integers \(x_i\) and \(y_i\), representing the coordinates of a point. The points are given in a random order.

outputFormat

Output a single number \(s\) (which may be a floating‐point number), computed as:

\[ s=\sum_{i=1}^{n-1}\left(\frac{d(P_{i-1},P_{i})}{v}\right)^2 \]

where \(P_0, P_1, \dots, P_{n-1}\) is the restored route (with \(P_0\) being the start and \(P_{n-1}\) the end) and \(d(P_{i-1},P_i)\) is the Euclidean distance between consecutive points.

sample

1 4
7 1
0 0
10 5
3 4

75.000000