Harta3

Observăm că relaţiile între puncte ne determină componente conexe de noduri ce au distantă fixă între ele. De asemenea, aceste componente se pot pune consecutiv pe axa Ox fără a ieşi din intervalul [-1 000 000, 1 000 000]. Astfel, avem trei cazuri:

• A şi B nu fac parte din nicio componentă, în această situaţie răspunsul este 1. Vom considera A de coordonate -1 000 000 şi B de coordonate -999 999. Restul componentelor îl vom pune consecutiv imediat după B.

• A şi B fac parte din aceeaşi componentă. Distanţa dintre A şi B este fixă în acest caz, şi vom amplasa restul componenteleor conescutiv în intervalul de soluţie.

• A şi B fac parte din componente diferite. În acest caz, ne vom fixa distanţa dintre A şi B, şi vom verifica în O(N) daca putem alatura componenta lui A de componenta lui B fără să se suprapună. Soluţia va fi determinata de cea mai mică distanţă valida. Ca şi în cazurile precendente, componentele rămase se pot pune consecutiv in intervalul de solţie fără a se intersecta.

Complexitatea este deci O(raspuns * N), unde prin raspuns ne referim la distanţa minimă dintre A şi B.