In primul rand, o explicatie etimologica. "Diagramele Voronoi" sunt o
aplicatie de geometrie analitica. Dandu-se o bucata din plan (de pilda
un dreptunghi) si niste puncte in dreptunghi, fiecarui punct ii revine
un domeniu (o "zona de influenta") constand din acele puncte care sunt
mai aproape de punctul in discutie decat de oricare alt punct. De
exemplu, daca avem doua puncte, ducem mediatoarea intre ele si
fiecarui punct ii revine punctele aflate de aceeasi parte cu el fata
de mediatoare. Pentru mai multe puncte, problema se complica.
Partitionarea dreptunghiului in zone de influenta se numeste diagrama
Voronoi. Probabil ca multora va suna cunoscuta problema. S-a dat la
barajul pentru lot de la ONI '97.

Acum despre oile noastre. Multumesc in mod special lui ****Vivi****,
care m-a ajutat sa-mi clarific rezolvarea in minte; fara el mi-ar
fi luat mult mai mult sa depasesc faza de "intuire" a rezolvarii.

In primul rand presupunem cunoscut algoritmul lui Dijkstra pentru
aflarea drumurilor minime de la "un nod" (sursa) la "fiecare din
celelalte". Am sa postez bineinteles algoritmul, dar numai daca
vor exista cereri in acest sens. Pentru referinte si pentru o
implementare simpla, a se vedea manualul domnului Sorin Tudor.

Problema noastra cere un Dijkstra generalizat, pentru ca se cere
drumul minim de la "una din fortarete" la "fiecare din celelalte
noduri". Reducerea ei la o problema rezolvabila cu Dijkstra clasic se
face considerand "din burta" o sursa S, pe care o unim cu muchii de
cost 0 cu fiecare fortareata. Apoi se aplica Dijkstra pentru sursa S.
Algoritmul este corect, demonstratia fiind ceva de genul:

Daca cel mai scurt drum de la S la catunul C trece prin fortareata F,
atunci in mod sigur F este cea mai apropiata fortareata de C. Daca
prin absurd ar exista o fortareata F' mai aproape de C, atunci drumul
S-F-C nu ar fi minim, existand drumul mai scurt S-F'-C. Contra-dictie.

Ca implementare, nu este nevoie sa ne chinuim sa simulam nodul in plus
S. Este suficient daca in algoritmul lui Dijkstra consideram de la
inceput toate fortaretele ca fiind vizitate si avand distanta 0 (cu
alte cuvinte, oricare din ele este o sursa). Pentru fiecare catun C
retinem fortareata cea mai apropiata. De notat ca nu intereseaza
drumul de la un catun la fortareata de care el apartine.

In sfarsit, o observatie. Mi s-a atras atentia ca declaratia

int A[180][180];

creeaza probleme in BC 3.1 daca se compileaza in modelul Small. Asa
este! :) O solutie era compliarea in modelul Huge. O alternativa,
chiar mai eleganta, pentru ca reduce memoria folosita de la O(N^2) la
O(M), este insa sa retinem graful nu ca pe o matrice de adiacenta, ci
ca pe un vector de liste de vecini. In acest caz listele se aloca
dinamic si nu mai apar probleme, pentru ca nu se mai aloca static
decat vectori, nu si matrice.

Asta e!