| Fişierul intrare/ieşire: | castori.in, castori.out | Sursă | Lot Bistrita 2009, Baraj 2 |
| Autor | Filip Cristian Buruiana | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.6 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/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.in | castori.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.
