centru

Centru

== include(page="template/taskheader" task_id="centru") ==

Poveste si cerinta...

Sa umbli prin cartier dupa un meci de fotbal este periculos si de aceea in diverse puncte ale acestuia s-au infiintat centre de prim-ajutor. Cartierul poate fi considerat ca fiind un caroiaj de dimensiune {$NxN$}, nodurile caroiajului fiind puncte avand coordonatele (abscisa, ordonata) din multimea {{$0, 1, ..., N-1$}}.
In $K$ noduri ale caroiajului s-au infiintat centre de prim-ajutor. Cand esti ranit in urma unei batai cu suporterii echipelor adverse (bataile au loc de asemenea numai in nodurile caroiajului) nu ai decat sa te duci la cel mai apropiat centru de prim-ajutor, unde vei primi ingrijiri medicale.
In urma conflictelor recente s-a decis infiintarea unui nou centru de prim-ajutor. Acesta trebuie sa fie plasat astfel incat sa se minimizeze distanta pana la cel mai apropiat centru in cazul cel mai defavorabil. Altfel spus, maximul dintre distantele de la un nod oarecare al caroiajului pana la cel mai apropiat centru de prim-ajutor sa fie minim.
 
h2. Cerinta
 
Scrieti un program care sa determine distanta maxima de la un nod al caroiajului la cel mai apropiat centru de prim-ajutor, dupa infiintarea noului centru.

h2. Date de intrare

...

Fisierul de intrare $centru.in$ contine pe prima linie doua numere naturale separate prin spatiu $N$ si {$K$}, cu semnificatia din enunt. Pe fiecare dintre urmatoarele $K$ linii se afla cate doua numere naturale cuprinse intre $0$ si {$N-1$}, separate prin spatiu, reprezentand abscisa, respectiv ordonata cate unui centru de prim-ajutor.

h2. Date de iesire

...

Fisierul de iesire $centru.out$ va contine pe prima linie un singur numar natural reprezentand distanta maxima de la un nod al caroiajului la cel mai apropiat centru de prim-ajutor, dupa infiintarea noului centru.

h2. Restrictii

* $... ≤ ... ≤ ...$

* {$1 ≤ N ≤ 1000$}
* {$1 &le; K < N*N$}
* Se considera ca distanta dintre doua noduri ale caroiajului ({$x{~1~},y{~1~}$}) si ({$x{~2~},y{~2~}$}) este distanta Manhattan {$|x{~1~}-x{~2~}| + |y{~1~}-y{~2~}|$}

h2. Exemplu
table(example). |_. centru.in |_. centru.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 7 5
0 1
1 4
3 6
5 0
5 5
| 3

|
h3. Explicatie

...

Noul centru se poate infiinta in nodul de coordonate ({$3,3$}). Orice alta solutie nu micsoreaza distanta maxima pana la cel mai apropiat centru de prim-ajutor in cazul cel mai defavorabil.
!problema/centru?centru.png!

== include(page="template/taskfooter" task_id="centru") ==

1963