== include(page="template/taskheader" task_id="reducere") ==
Se dă o listă de $N$ puncte în plan prin coordonatele lor carteziene. Fiecare dintre aceste puncte are asociată o greutate notată $G[~P~]$ care inițial este [$1$]. Asupra listei de puncte se efectuează următorul tip de operație: se aleg două puncte diferite $A4 și $B$ și pe baza acestora se determină un al treilea punct $C$ cu caracteristicile:
$X[~C~] = (G[~A~] * X[~A~] + G[~B~] * X[~B~]) / (G[~A~] + G[~B~])$
$Y[~C~] = (G[~A~] * Y[~A~] + G[~B~] * Y[~B~]) / (G[~A~] + G[~B~])$
$G[~C~] = G[~A~] + G[~B~]$
iar costul acestei operații este $G[~A~] * G[~B~] * Dist(A, B)$. Apoi se elimină din listă punctele $A$ și $B$ și se adaugă punctul [$C$]. Acest tip de operație se efectuează succesiv (de $N - 1$ ori) până când lista va conține un singur punct.
h2. Cerință
Determinați costul total minim al unei secvențe de operații prin care să rămâneți cu un singur punct în listă.
$XC = (GA * XA + GB * XB) / (GA + GB)$
$YC = (GA * YA + GB * YB) / (GA + GB)$
$GC = GA + GB$
iar costul acestei operații este $GA * GB * Dist(A, B)$. Apoi se elimină din listă punctele $A$ și $B$ și se adaugă punctul [$C$]. Acest tip de operație se efectuează succesiv (de $N - 1$ ori) până când lista va conține un singur punct.
h2. Date de intrare
Fișierul de intrare $reducere.in$ conține pe prima linie numărul natural [$N$]. Pe următoarele $N$ linii sunt date cele $N$ puncte [$P1$], [$P2$], ..., $PN$ prin coordonatele lor carteziene $X[~Pi~]$ și $Y[~Pi~]$, numere naturale, câte unul pe câte o linie.
Fișierul de intrare $reducere.in$ ...
h2. Date de ieșire
Fișierul de ieșire $reducere.out$ conține un singur număr zecimal, costul total minim al unei secvențe de operații prin care să rămâneți cu un singur punct în listă, cu o precizie absolută de 10{#-4#}.
În fișierul de ieșire $reducere.out$ ...
h2. Restricții
* $2 ≤ N ≤ 16$
* $-10 000 ≤ XPi, YPi ≤ 10 000$
* Pentru 30% din teste se garantează că $2 ≤ N ≤ 8$
* Lista poate conține inițial sau pe parcurs două sau mai multe puncte cu aceleași coordonate.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example).
|_. reducere.in |_. reducere.out |
| 4
0 0
0 1
1 0
1 1
| 2.8284
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicație
Se aleg $P1$ și $P4$ și se obține punctul $P5$ de coordonate $(0.5, 0.5)$ cu costul $~1.4142$ și greutatea [$2$].
Se aleg $P2$ și $P3$ și se obține punctul $P6$ de coordonate $(0.5, 0.5)$ cu costul $~1.4142$ și greutatea [$2$].
Se aleg $P5$ și $P6$ și se obține punctul $P7$ de coordonate $(0.5, 0.5)$ cu costul $0.0000$ și greutatea [$4$].
Costul total este $~2.8284$.
...
== include(page="template/taskfooter" task_id="reducere") ==
