== include(page="template/taskheader" task_id="castori") ==
Poveste şi cerinţă...
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.
h2. 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 $(x{~1~} y{~1~})$ şi $(x{~2~} y{~2~})$ se va înţelege distanţa Manhattan $|x{~1~} - x{~2~}| + |y{~1~} - y{~2~}|$.
h2. Date de intrare
Fişierul de intrare $castori.in$ ...
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.
h2. Date de ieşire
În fişierul de ieşire $castori.out$ ...
Pe prima linie a fişierului de ieşire $castori.out$ se va scrie distanţa cerută.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ C ≤ N ≤ 10 000$
* Coordonatele vizuinelor vor fi numere întregi din intervalul $[-10^8^, +10^8^]$.
* Nu vor exista două vizuine în acelaşi punct.
h2. Exemplu
table(example). |_. castori.in |_. castori.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 5 3
2 9
-1 -5
6 -3
8 4
-2 2
| 12
|
h3. 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$.
== include(page="template/taskfooter" task_id="castori") ==
