P3517 [POI 2011] WYK-Plot

We call any sequence of points in the plane a plot. We intend to replace a given plot $(P_1,\cdots,P_n)$ with another that will have at most $m$ points ($m\le n$) in such a way that it "resembles" the original plot best. The new plot is created as follows. The sequence of points $P_1,\cdots,P_n$ can be partitioned into $s$ ($s\le m$) contiguous subsequences: $(P_{k_0+1},\cdots,P_{k_1}),(P_{k_1+1},\cdots,P_{k_2}),\cdots,(P_{k_{s-1}+1},\cdots,P_{k_s})$ where $0=k_0

In the first line of the standard input there are two integers $n$ and $m$, $1\le m\le n\le 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\le x_i,y_i\le 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\le s\le m$. Next, the following $s$ lines should specify the coordinates of the points $Q_1,\cdots,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.