== include(page="template/taskheader" task_id="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.
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~}|$.
Poveste şi cerinţă...
h2. 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.
Fişierul de intrare $castori.in$ ...
h2. Date de ieşire
Pe prima linie a fişierului de ieşire $castori.out$ se va scrie distanţa cerută.
În fişierul de ieşire $castori.out$ ...
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 |
| 5 3
2 9
-1 -5
6 -3
8 4
-2 2
| 12
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
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") ==
