9058번 - Maximum Detour 다국어채점 준비 중

 Consider a geometric graph G = (V, E) which is just a path of N vertices. More precisely, V = {v₁, v₂, … , v_N} and E = {v_iv_i+1 | 1≤ i ≤ N-1}. Also, in a geometric graph each vertex in V is represented by a point on the plane and each edge in E by a straight line segment connecting two points corresponding to two vertices.

If we regard G as a road network on our plane so that we are allowed to move only on the network, then it will make some detours when moving on G compared to the direct path between two points. To measure such quantity, define the detour D(G, v_i , v_j) between two vertices v_i , v_j in V with i < j as follows:

D(G, v_i , v_j) = dG(v_i , v_j) / d(v_i , v_j),

where dG(v_i, v_j) = d(v_i , v_i+1) + d(v_i+1, v_i+2) + … + d(v_j-1, v_j) and d(·, ·) denotes the Euclidean distance function. Further, we denote by D(G) the maximum detour of geometric graph G among all the pairs of vertices of G:

D(G) = max {D(G, v, w) | v, w ∈V, v ≠ w}.

In figure above, a geometric graph G is seen as a path of 7 vertices {v₁, ..., v₇}. Numbers indicate the Euclidean distances between pairs of vertices; for instance, d(v₁, v₂) = 10 and d(v₁, v₄) = 4. Here, you can see that D(G, v₁, v₄) = dG(v₁, v₄) / d(v₁, v₄) = (10 + 10 + 9) / 4 = 29/4.

In this problem, you will be given a sequence of N points and two consecutive points are supposed to be connected by an edge which is represented by a straight line segment. Then, you are to compute the maximum detour D(G) of a given geometric graph G. 

Your program is to read from standard input. The input consists of T (1 ≤ T ≤ 20) test cases. The number T of test cases is given in the first line of the input. Each test case contains the number N (2 ≤ N ≤ 10000) of vertices of a given geometric graph G (which is a path) at first line, and the coordinates of the vertices following line by line. The coordinates of each vertex are bounded in the range [-10000...10000]. All the primitive input values are given as integers and integers in a line are separated by a single space. 

Your program is to write to standard output. Print exactly one line for each test case with the maximum detour D(G) of G. The output should contain only two decimal places just by rounding off. Note that G may be possibly self-intersected by its edges, and if D(G) value is at least 1000, you MUST print out “TOO LARGE”, instead of the value of D(G).