| Fişierul intrare/ieşire: | segmente2.in, segmente2.out | Sursă | RMI 2014 |
| Autor | Vlad Duta | Adăugată de |  Marius Dum •rmi_2014 |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Segmente2
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.
Date de intrare
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.
Date de ieşire
Î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).
Restricţii
- 2 ≤ N ≤ 5000
- 1 ≤ K ≤ N(N+1)/2
- 1 ≤ K ≤ 100
- toate coordonatele sunt numere intregi din intervalul [-109, 109]
- coordonatele punctelor nu sunt neaparat distincte
Exemplu
| segmente2.in | segmente2.out |
|---|---|
| 6 3 1 2 4 5 2 3 1 1 8 8 7 4 | 4.65028 0 2 3 |
