Fişierul intrare/ieşire:segmente2.in, segmente2.outSursăRMI 2014
AutorVlad DutaAdăugată dermi_2014Marius Dum rmi_2014
Timp execuţie pe test1.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.insegmente2.out
6 3
1 2
4 5
2 3
1 1
8 8
7 4
4.65028
0
2
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?