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!