Fişierul intrare/ieşire:centrale.in, centrale.outSursăConcursul National de Informatica "Adolescent Grigore Moisil" 16
AutorChichirim GeorgeAdăugată deAGMinformaticaAGMInformatica •AGMinformatica
Timp execuţie pe test1.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Centrale Nucleare

In tara Smecheriei s-au construit N centrale nucleare, numerotate de la 1 la N, pentru a furniza enrgie electrica intregii tari. Fiecare centrala i se afla la pozitia (xi,yi) in plan. In ciuda smecheriei populatiei tarii, acestia nu s-au hotarat si pe care centrale o sa le puna in functiune, doar stiu ca in functie de constructia si amplasarea acestora exista M restrictii de forma: cel putin una din centralele a si b trebuie puse in functiune. Datorita banului gros de care dau dovada cetatenii acestei tari, nu s-a pus problema sigurantei si utilitatii acestor centrale inainte de constructie si, prin urmare, cateva centrale nu vor fi folosite din cauza sigurantei. Scopul vostru este sa determinati distanta maxima D astfel incat sa se poata alege o multime de centrale care sa fie puse in functiune astfel incat, din motive de siguranta, distanta Manhattan intre oricare doua centrale alese sa fie mai mare sau egala cu D.

Date de intrare

Fişierul de intrare centrale.in contine pe prima linie doua numere naturale N (numarul de centrale) si M(numarul de restrictii). Pe urmatoarele N linii se afla cate doua valori (xi,yi) reprezentand coordonatele la care se afla centrala i. Pe urmatoarele M linii se afla cate doua numere naturale a si b cu semnificatia ca cel putin o centrala dintre a si b trebuie aleasa.

Date de ieşire

În fişierul de ieşire centrale.out se va afisa numarul intreg D.

Restricţii

  • 1 ≤ N ≤ 7000
  • 1 ≤ M ≤ 30000
  • 1 ≤ xi, yi ≤ 106
  • 1 ≤ a, b ≤ N
  • Coodronatele la care se afla centralele sunt distincte doua cate doua
  • Distanta Manhattan intre 2 puncte (x1,y1) si (x2,y2) este abs(x1-x2)+abs(y1-y2)

Exemplu

centrale.incentrale.out
6 4
2 3
6 7
8 4
5 2
4 6
6 4
1 4
4 6
6 3
5 2
5

Explicaţie

Putem alege centralele 3, 4 si 5. Distanta minima intre oricare doua este 5.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?