8206번 - Plot 스페셜 저지다국어

We call any sequence of points in the plane a plot. We intend to replace a given plot (P₁,…,P_n) with another that will have at most m points (m ≤ n) in such a way that it "resembles" the original plot best.

The new plot is created as follows. The sequence of points P₁,…,P_n can be partitioned into  s (s ≤ m) contiguous subsequences:

    (P_{ko+1},…,P_k1), (P_{k1+1},…,P_k2), …, (P_{k(s-1)+1},…,P_ks)

where 0 = k₀ < k₁ < k₂ < … < k_s = n, and afterwards each subsequence (P_k(i-1)+1,…,P_ki), for i=1,…,s, is replaced by a new point Q_i. In that case we say that each of the points P_k(i-1)+1,…,P_ki has been contracted to the point Q_i. As a result a new plot, represented by the points Q₁,…,Q_s, is created. The measure of such plot's resemblance to the original is the maximum distance of all the points P₁,…,P_n to the point it has been contracted to:

    \( \max_{i=1Idots,s} {\left(\max_{j=k_{i-1}+1,...,k_i} {(d(P_j,Q_i))}\right)} \)

where d(P_j,Q_i) denotes the distance between P_j and Q_i, given by the well-known formula:

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

An exemplary plot (P₁,…,P₇) and the new plot (Q₁,Q₂), where (P₁,…,P₄) are contracted to Q_1, whereas (P₅,P₆,P₇) to Q₂.

For a given plot consisting of n points, you are to find the plot that resembles it most while having at most m points, where the partitioning into contiguous subsequences is arbitrary. Due to limited precision of floating point operations, a result is deemed correct if its resemblance to the given plot is larger than the optimum resemblance by at most 0.000001.

In the first line of the standard input there are two integers n and m, 1 ≤ m ≤ n ≤ 100,000, separated by a single space. Each of the following n lines holds two integers, separated by a single space. The (i+1)-th line gives x_i,y_i, -1,000,000 ≤ x_i,y_i ≤ 1,000,000, denoting the coordinates (x_i,y_i) of the point P_i.

In the first line of the standard output one real number d should be printed out, the resemblance measure of the plot found to the original one. In the second line of the standard output there should be another integer s, 1 ≤ s ≤ m. Next, the following s lines should specify the coordinates of the points Q₁,…,Q_s, one point per line. Thus the (i+2)-th line should give two real numbers u_i and v_i, separated by a single space, that denote the coordinates (u_i,v_i) of the point Q_i. All the real numbers should be printed with at most 15 digits after the decimal point.