== include(page="template/taskheader" task_id="segmente2") ==
Poveste şi cerinţă...
Vlad a desenat $N$ puncte in plan, la coordonate intregi, numerotate in ordine de la 0 la N-1. El vrea sa traseze $K$ segmente distincte avand fiecare capetele in 2 puncte dintre cele N, astfel incat suma lungimilor celor K segmente sa fie minima. Tu vei incearca acum sa determini lungimea totala minima a celor $K$ segmente, precum si punctele care apartin cel putin unui segment, indiferent cum ar trasa Vlad cele $K$ segmente.
h2. Date de intrare
Fişierul de intrare $segmente2.in$ ...
Fişierul de intrare $segmente2.in$ contine pe prima linie 2 numere naturale $N$ si $K$, iar pe urmatoarele N linii se afla cate doua numere intregi $Xi$, $Yi$ reprezentand coordonatele fiecarui punct.
h2. Date de ieşire
În fişierul de ieşire $segmente2.out$ ...
În fişierul de ieşire $segmente2.out$ veti afisa pe prima linie lungimea totala minima a celor K segmente, cu o precizie de $5 zecimale exacte$. Apoi se vor afisa separat pe cate o linie si in ordine crescatoare numerele de ordine ale punctelor care vor apartine cel putin unuia din cele K segmente, indiferent cum ar fi acestea trasate (Daca am elimina oricare dintre aceste puncte, atunci nu am mai reusi sa obtinem o solutie la fel de buna cu punctele ramase).
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ N ≤ 5000$
* $1 ≤ K ≤ N(N+1)/2$
* $1 ≤ K ≤ 100$
* toate coordonatele sunt numere intregi din intervalul [-10^9^, 10^9^]
* coordonatele punctelor nu sunt neaparat distincte
h2. Exemplu
table(example). |_. segmente2.in |_. segmente2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 3
1 2
4 5
2 3
1 1
8 8
7 4
| 4.65028
0
2
3
|
h3. Explicaţie
...
== include(page="template/taskfooter" task_id="segmente2") ==
== include(page="template/taskfooter" task_id="segmente2") ==
