Fişierul intrare/ieşire:castori.in, castori.outSursăLot Bistrita 2009, Baraj 2
AutorFilip Cristian BuruianaAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test1.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Castori

Pe o câmpie întinsă oarecare sunt C castori şi N vizuine ce pot fi reprezentate ca puncte laticiale în plan. Castorii trebuie să îşi aleagă fiecare câte o vizuină unde pot să se ascundă în caz de pericol. Se ştie că o vizuină nu poate adăposti mai mult de un castor. Castorii doresc să îşi aleagă vizuinele astfel încât cele mai îndepărtate două vizuine din cele selectate să fie cât mai apropiate posibil.

Cerinţă

Să se selecteze C dintre cele N vizuine astfel încât maximul distanţelor dintre oricare două selectate să fie minim posibil. Prin distanţa între două puncte (x1 y1) şi (x2 y2) se va înţelege distanţa Manhattan |x1 - x2| + |y1 - y2|.

Date de intrare

Pe prima linie a fişierului de intrare castori.in se află două numere naturale N şi C, cu semnificaţia din enunţ. Fiecare din urmatoarele N linii conţine câte o pereche de numere întregi x y, reprezentând coordonatele unei vizuine.

Date de ieşire

Pe prima linie a fişierului de ieşire castori.out se va scrie distanţa cerută.

Restricţii

  • 2 ≤ C ≤ N ≤ 10 000
  • Coordonatele vizuinelor vor fi numere întregi din intervalul [-108, +108].
  • Nu vor exista două vizuine în acelaşi punct.

Exemplu

castori.incastori.out
5 3
2 9
-1 -5
6 -3
8 4
-2 2
12

Explicaţie

Se vor selecta vizuinele 1, 4 şi 5. Distanţa între oricare două va fi:

  • distanţă(1, 4) = |2 - 8| + |9 - 4| = 11
  • distanţă(1, 5) = |2 - (-2)| + |9 - 2| = 11
  • distanţă(4, 5) = |8 - (-2)| + |4 - 2| = 12

Oricum am selecta alte 3 vizuine, distanţa dintre cele mai îndepărtate două este mai mare decât 12.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content