Za dati skup tačaka u ravni odrediti koliko je rastojanje između dve tačke koje su međusobno najbliže.
Sa standardnog ulaza se unosi broj tačaka \(n\) (\(1\leq n \leq 50000\)), a zatim u narednih \(n\) redova koordinate tačaka (dva cela broja između \(-10^9\) i \(10^9\), razdvojena razmakom).
Na standardni izlaz ispisati traženo rastojanje, zaokruženo na pet decimala.
5 0 0 0 2 2 0 2 2 1 1
1.41421
Rešenje grubom silom podrazumeva ispitivanje svih parova tačaka i složenost mu je \(O(n^2)\).
struct Tacka {
int x, y;
};
double rastojanje(const Tacka& t1, const Tacka& t2) {
double dx = t1.x - t2.x;
double dy = t1.y - t2.y;
return sqrt(dx*dx + dy*dy);
}
double najblizeTacke(vector<Tacka>& tacke) {
int n = tacke.size();
double d = numeric_limits<double>::max();
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
d = min(d, rastojanje(tacke[i], tacke[j]));
return d;
}#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
struct Tacka {
int x, y;
};
double rastojanje(const Tacka& t1, const Tacka& t2) {
double dx = t1.x - t2.x;
double dy = t1.y - t2.y;
return sqrt(dx*dx + dy*dy);
}
double najblizeTacke(vector<Tacka>& tacke) {
int n = tacke.size();
double d = numeric_limits<double>::max();
for (int i = 0; i < n; i++)
for (int j = i+1; j < n; j++)
d = min(d, rastojanje(tacke[i], tacke[j]));
return d;
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<Tacka> tacke(n);
for (int i = 0; i < n; i++)
cin >> tacke[i].x >> tacke[i].y;
cout << fixed << showpoint << setprecision(5)
<< najblizeTacke(tacke) << endl;
return 0;
}Jedan način da se do rešenja dođe efikasnije je da se primeni dekompozicija.
Bazni slučaj predstavlja situacija u kojoj imamo manje od četiri tačke, jer njih ne možemo podeliti u dve polovine u kojima postoji bar po jedan par tačaka. U tom slučaju rešenje nalazimo poređenjem rastojanja svih parova tačaka (pošto je tačaka malo, ovaj korak je složenosti \(O(1)\)). Ukoliko u skupu nema tačaka ili postoji samo jedna tačka, smatraćemo da je rezultat \(\infty\).
Skup tačaka možemo jednom vertikalnom pravom podeliti na dve otprilike istobrojne polovine. Ako u fazi pretprocesiranja tačke sortiramo po koordinati \(x\), vertikalna prava može odgovarati koordinati središnje tačke. Rekurzivno određujemo najmanje rastojanje u prvoj polovini (te tačke se nalaze levo od vertikalne prave ili eventualno na njoj) i najmanje rastojanje u drugoj polovini (te tačke se nalaze desno od vertikalne prave ili eventualno na njoj). Najbliži par je takav da su (1) obe tačke u levoj polovini, (2) obe tačke u desnoj polovini ili (3) jedna tačka je u levoj, a druga u desnoj polovini. Za prva dva slučaja već znamo rešenja (na osnovu rezultata rekurzivnih poziva) i ostaje da se razmotri samo treći.
Neka je \(d_l\) minimalno rastojanje tačaka u levoj polovini, \(d_r\) minimalno rastojanje tačaka u desnoj polovini, a \(d\) minimum ta dva rastojanja. Ako vertikalna prava ima \(x\)-koordinatu \(x\), tada je moguće primeniti tehniku odsecanja i odbaciti sve tačke koje su levo od \(x-d\) i desno od \(x+d\), jer je njihovo rastojanje do najbliže tačke iz suprotne polovine sigurno veće od \(d\). Potrebno je ispitati sve preostale tačke, tj. sve tačke iz pojasa \([x-d, x+d]\), proveriti da li među njima postoji neki par tačaka čije je rastojanje strogo manje od \(d\) i vrednost \(d\) ažurirati na vrednost najmanjeg rastojanja takvog para tačaka. Ako su tačke nasumično raspoređene, većina tačaka će biti van tog pojasa. Međutim, problem je to što u najgorem slučaju u pojasu može biti puno tačaka (moguće je čak i da se svih \(n\) tačaka nađe u tom pojasu) i ako ispitujemo sve parove, tada dolazimo do oko \(n^2/4\) poređenja (ako je pola tačaka levo, a pola desno od prave podele). Ipak, proveru je moguće organizovati tako da se proveri samo mali broj parova tačaka.
Jednostavnosti radi pretpostavićemo da na isti način razmatramo sve tačke unutar pojasa \([x-d, x+d]\), bez obzira sa koje strane vertikalne prave se nalaze (unapred znamo da je provera tačaka koje su sa iste strane vertikalne prave podele nepotrebna, ali ne može narušiti korektnost, dok god smo sigurni da se porede i svi potrebni parovi tačaka sa različite strane te prave). Svaku tačku \(A\) iz pojasa je dovoljno uporediti samo sa onim tačkama koje leže unutar kruga sa centrom u tački \(A\) i poluprečnikom \(d\), jer su sve tačke van tog kruga sigurno od tačke \(A\) udaljene više od \(d\), što omogućava značajna odsecanja. Međutim, pripadnost krugu nije jednostavno proveriti i zato umesto njega možemo razmatrati kvadrat stranice dužine \(2d\), čiji se centar nalazi na pravoj \(y=x\), a na čijoj se horizontalnoj srednjoj liniji nalazi tačka \(A\) i tačku \(A\) ćemo porediti samo sa tačkama unutar tog kvadrata (znamo da su tačke van tog kvadrata sigurno na rastojanju većem od \(d\)). Time će odsecanja biti nešto manje nego u slučaju kruga (jer su neke tačke unutar kvadrata na rastojanju većem od \(d\)), ali će detektovanje tačaka koje pripadaju tom kvadratu biti veoma jednostavno – to će biti sve one tačke iz pojasa \([x-d, x+d]\), kojima je koordinata \(y\) u intervalu \([y_A - d, y_A + d]\).
Dodatno smanjenje broja poređenja možemo dobiti ako primetimo da svaki par obrađujemo dva puta (jednom dok obrađujemo tačke u okolini prve, a jednom dok obrađujemo tačke u okolini druge tačke). Možemo jednostavno zaključiti da je dovoljno svaku tačku \(A\) porediti samo sa onim tačkama koje se su iznad nje (ili su eventualno na istoj visini kao ona), tj. ne u celom kvadratu, nego samo u njegovoj gornjoj polovini. Dakle, svaku tačku \(A\) je potrebno uporediti samo sa tačkama čije \(x\) koordinate leže unutar intervala \([x-d, x+d]\) i čije \(y\) koordinate leže unutar intervala \([y_A, y_A + d]\). Prvi uslov možemo obezbediti tako što pre poređenja sve tačke iz pojasa širine \(d\) oko vertikalne prave podele izdvojimo u poseban niz (za to nam je potrebno \(O(n)\) dodatne memorije i vremena). Drugi uslov efikasnije možemo obezbediti ako sve tačke tog pomoćnog niza sortiramo po koordinati \(y\) (za to nam je potrebno vreme \(O(n\log{n})\) i zatim tačke obrađujemo u neopadajućem redosledu \(y\) koordinata. Za svaku tačku \(A\) obrađujemo samo tačke koje se nalaze nakon nje u sortiranom nizu i obrađujemo jednu po jednu tačku sve dok ne naiđemo na tačku čija je koordinata \(y\) veća ili jednaka od vrednosti \(y_A + d\) (ona od tačke \(A\) ne može biti na manjem rastojanju od \(d\), a isto važi i za sve tačke u nizu iza nje).
// funkcija pronalazi najblizi par tacaka u delu nizu [l, r]
double najblizeTacke(vector<Tacka>& tacke, int l, int r,
vector<Tacka>& pojas) {
// za manje od 4 tacke najblizi par odredjujemo grubom silom
if (r - l + 1 < 4) {
double d = numeric_limits<double>::max();
for (int i = l; i < r; i++)
for (int j = i+1; j <= r; j++)
d = min(d, rastojanje(tacke[i], tacke[j]));
return d;
}
// delimo niz tacaka sa pozicija [l, r] u dve polovine
int s = l + (r - l) / 2;
// rekurzivno pronalazimo najblizi par u
// levoj i desnoj polovini niza
double d1 = najblizeTacke(tacke, l, s, pojas);
double d2 = najblizeTacke(tacke, s+1, r, pojas);
// najmanje rastojanje svih parova tacaka
double d = min(d1, d2);
// pronalazimo tacke u pojasu sirine 2d oko sredisnje linije
double dl = tacke[s].x - d, dr = tacke[s].x + d;
int k = 0;
for (int i = l; i <= r; i++)
if (dl <= tacke[i].x && tacke[i].x <= dr)
pojas[k++] = tacke[i];
// sortiramo tacke u pojasu po y koordinati
sort(begin(pojas), next(begin(pojas), k),
[](const Tacka& t1, const Tacka& t2) {
return t1.y < t2.y;
});
// analiziramo sve tacke u pojasu
for (int i = 0; i < k; i++)
// svaku tacku poredimo samo sa onim tackama koje su u
// pravougaoniku iznad nje
for (int j = i+1; j < k && pojas[j].y-pojas[i].y < d; j++)
d = min(d, rastojanje(pojas[i], pojas[j]));
// vracamo najkrace rastojanje
return d;
}
double najblizeTacke(vector<Tacka>& tacke) {
// sortiramo tacke po x koordinati
sort(begin(tacke), end(tacke),
[](const Tacka& t1, const Tacka& t2) {
return t1.x < t2.x;
});
// pomocni niz (alociramo ga samo jednom, van rekurzije)
vector<Tacka> pojas(tacke.size());
return najblizeTacke(tacke, 0, tacke.size() - 1, pojas);
}#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <utility>
#include <limits>
#include <cmath>
using namespace std;
struct Tacka {
int x, y;
};
double rastojanje(const Tacka& t1, const Tacka& t2) {
double dx = t1.x - t2.x;
double dy = t1.y - t2.y;
return sqrt(dx*dx + dy*dy);
}
// funkcija pronalazi najblizi par tacaka u delu nizu [l, r]
double najblizeTacke(vector<Tacka>& tacke, int l, int r,
vector<Tacka>& pojas) {
// za manje od 4 tacke najblizi par odredjujemo grubom silom
if (r - l + 1 < 4) {
double d = numeric_limits<double>::max();
for (int i = l; i < r; i++)
for (int j = i+1; j <= r; j++)
d = min(d, rastojanje(tacke[i], tacke[j]));
return d;
}
// delimo niz tacaka sa pozicija [l, r] u dve polovine
int s = l + (r - l) / 2;
// rekurzivno pronalazimo najblizi par u
// levoj i desnoj polovini niza
double d1 = najblizeTacke(tacke, l, s, pojas);
double d2 = najblizeTacke(tacke, s+1, r, pojas);
// najmanje rastojanje svih parova tacaka
double d = min(d1, d2);
// pronalazimo tacke u pojasu sirine 2d oko sredisnje linije
double dl = tacke[s].x - d, dr = tacke[s].x + d;
int k = 0;
for (int i = l; i <= r; i++)
if (dl <= tacke[i].x && tacke[i].x <= dr)
pojas[k++] = tacke[i];
// sortiramo tacke u pojasu po y koordinati
sort(begin(pojas), next(begin(pojas), k),
[](const Tacka& t1, const Tacka& t2) {
return t1.y < t2.y;
});
// analiziramo sve tacke u pojasu
for (int i = 0; i < k; i++)
// svaku tacku poredimo samo sa onim tackama koje su u
// pravougaoniku iznad nje
for (int j = i+1; j < k && pojas[j].y-pojas[i].y < d; j++)
d = min(d, rastojanje(pojas[i], pojas[j]));
// vracamo najkrace rastojanje
return d;
}
double najblizeTacke(vector<Tacka>& tacke) {
// sortiramo tacke po x koordinati
sort(begin(tacke), end(tacke),
[](const Tacka& t1, const Tacka& t2) {
return t1.x < t2.x;
});
// pomocni niz (alociramo ga samo jednom, van rekurzije)
vector<Tacka> pojas(tacke.size());
return najblizeTacke(tacke, 0, tacke.size() - 1, pojas);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<Tacka> tacke(n);
for (int i = 0; i < n; i++)
cin >> tacke[i].x >> tacke[i].y;
cout << fixed << showpoint << setprecision(5)
<< najblizeTacke(tacke) << endl;
return 0;
}Odredimo složenost prethodnog algoritma. Algoritam se sastoji od dva rekurzivna poziva za dvostruko manju dimenziju niza tačaka i faze dobijanja krajnjeg rezultata na osnovu rezultata rekurzivnih poziva i dodatne analize tačaka u pojasu \([x-d, x+d]\). Već smo konstatovali da izdvajanje tačaka centralnog pojasa zahteva \(O(n)\) memorije i vremena i da sortiranje tih tačaka po koordinati \(y\) zahteva dodatnih \(O(n\log{n})\) koraka. Ostaje još da se proceni složenost ugnežđenih petlji u kojima se porede tačke unutar pojasa. Iako deluje da je složenost kvadratna, elementarnim geometrijskim rezonovanjem dokazaćemo da je složenost tog koraka linearna tj. \(O(n)\) i da se u svakom koraku spoljašnje petlje unutrašnja petlja može izvršiti samo veoma mali broj puta (dokazaćemo da je taj broj izvršavanja ograničen odozgo sa 7, mada je u praksi on često i dosta manji od toga i za nasumično generisane tačke ta petlja se najčešće izvršava 0, 1 ili eventualno 2 puta).
Za svaku tačku \(A\) možemo konstruisati 8 kvadrata dimenzije \(d/2\), kao što je prikazano na slici (kvadrati su upisani u pojas \([x-d, x+d]\), u dva reda od po četiri kvadrata i tačka \(A\) leži na donjoj ivici donjih kvadrata).
Najveće rastojanje između dve tačke unutar nekog kvadrata se postiže kada oni leže u njegovim naspramnim temenima, a pošto je dužina dijagonale kvadrata stranice \(\frac{d}{2}\) jednaka \(\frac{d\sqrt{2}}{2} \approx 0,70711 \cdot d\), rastojanje između svake dve tačke unutar istog kvadrata je strogo manje od \(d\). Pošto svi kvadrati leže bilo potpuno sa leve strane vertikalne prave podele, bilo potpuno sa njene desne strane, unutar svakog od kvadrata može se naći najviše jedna tačka našeg skupa (u suprotnom bi se bilo sa leve, bilo sa desne strane centralne prave podele nalazio par tačaka sa rastojanjem strogo manjim od \(d\), što je kontradiktorno sa definicijom veličine \(d\)). To znači da se iznad tačke \(A\) može nalaziti najviše 7 tačaka koje pripadaju ostalim kvadratima (sama tačka \(A\) već pripada jednom od kvadrata) i da se sve ostale tačke koje su iznad \(A\) nalaze i iznad naših kvadrata, što znači da im je rastojanje od \(A\) sigurno veće od \(d\) (jer im je vertikalno rastojanje veće od \(d\)) i njih nije potrebno razmatrati.
Tačke koje su sa iste strane prave podele kao i tačka \(A\) možemo prosto preskočiti u telu unutrašnje petlje i tako uštediti na računanju njihovog rastojanja od tačke \(A\), ali to neće promeniti red složenosti algoritma. Druga mogućnost za implementaciju je da ne čuvamo sve tačke iz pojasa u istom skupu, već da ih podelimo u dva pojasa i da zatim obradimo najpre sve tačke iz levog pojasa gledajući rastojanja u odnosu na naredne najviše 4 tačke iz desnog pojasa, a zatim da obradimo sve tačke iz desnog pojasa gledajući rastojanja u odnosu na najviše 4 tačke iz levog pojasa (jer u suprotnom pojasu postoji 4 kvadrata dimezije \(d/2\), za koje smo dokazali da ne mogu da sadrže dve tačke istovremeno). Implementacija na taj način je malo komplikovanija, a red složenosti algoritma ostaje isti (i eksperimenti ne ukazuju na značajne dobitke).
Dakle, nakon rekurzivnih poziva, za dobijanje konačnog rezultata je potrebno izvršiti dodatnih \(O(n\log{n})\) koraka i dekompozicija zadovoljava rekurentnu jednačinu \(T(n) = 2T(n/2) + O(n\log{n})\). Rešenje ove jednačine, na osnovu master teoreme, je \(O(n(\log{n})^2)\).
Složenost opisanog algoritma može se popraviti ako se sortiranje po koordinati \(y\) vrši istovremeno sa pronalaženjem najbližeg para tačaka, tj. ako se ojača induktivna hipoteza i ako se pretpostavi da će rekurzivni poziv vratiti rastojanje između najbliže dve tačke i ujedno sortirati date tačke po koordinati \(y\). U koraku objedinjavanja dva sortirana niza objedinjujemo u jedan. To možemo uraditi uobičajenim algoritmom objedinjavanja, zasnovanom na tehnici dva pokazivača, koji objedinjavanje vrši u linearnoj složenosti. U jeziku C++ taj algoritam je dostupan i pomoću bibliotečke funkcije merge. Na taj način dobijamo algoritam koji zadovoljava jednačinu \(T(n) = 2T(n/2) + O(n)\) i složenosti je \(O(n\log{n})\). Naglasimo da ova optimizacija nije revolucionarna, ali može malo poboljšati efikasnost.
Na nivou implementacije, malo poboljšanje bismo mogli dobiti i tako što bismo izbegli alokacije pomoćnog vektora unutar rekurzivnih poziva i kod izmeniti tako da se u svakom rekurzivnom pozivu koristi isti, unapred alociran pomoćni vektor. Još jedna moguća optimizacija o kojoj bi se moglo razmisliti je smanjivanje broja operacija korenovanja.
bool porediX(const Tacka& t1, const Tacka& t2) {
return t1.x < t2.x;
}
bool porediY(const Tacka& t1, const Tacka& t2) {
return t1.y < t2.y;
}
// funkcija pronalazi najblizi par tacaka u delu nizu [l, r] i
// dodatno sortira tacke unutar tog dela niza po y koordinati
double najblizeTacke(vector<Tacka>& tacke, int l, int r,
vector<Tacka>& pojas) {
// za manje od 4 tacke, grubom silom odredjujemo najblizi par
if (r - l + 1 < 4) {
// odredjujemo najblizi par
double d = numeric_limits<double>::max();
for (int i = l; i < r; i++)
for (int j = i+1; j <= r; j++)
d = min(d, rastojanje(tacke[i], tacke[j]));
// sortiramo tacke po y-koordinati
sort(next(begin(tacke), l), next(begin(tacke), r+1),
porediY);
return d;
}
// delimo niz tacaka sa pozicija [l, r] u dve polovine
int s = l + (r - l) / 2;
int x = tacke[s].x;
// rekurzivno pronalazimo najblizi par u levoj i desnoj
// polovini niza sortirajuci te polovine po y koordinati
double d1 = najblizeTacke(tacke, l, s, pojas);
double d2 = najblizeTacke(tacke, s+1, r, pojas);
// najmanje rastojanje svih parova tacaka
double d = min(d1, d2);
// objedinjavamo dva sortirane polovine
// (koristimo niz pojas kao pomocni)
merge(next(begin(tacke), l), next(begin(tacke), s+1),
next(begin(tacke), s+1), next(begin(tacke), r+1),
begin(pojas), porediY);
copy(begin(pojas), next(begin(pojas), r-l+1),
next(begin(tacke), l));
// pronalazimo tacke u pojasu sirine 2d oko sredisnje linije
int k = 0;
double dl = x - d, dr = x + d;
for (int i = l; i <= r; i++)
if (dl <= tacke[i].x && tacke[i].x <= dr)
pojas[k++] = tacke[i];
// analiziramo sve tacke u pojasu
for (int i = 0; i < k; i++)
// svaku tacku poredimo samo sa onim tackama koje su u
// pravougaoniku iznad nje
for (int j = i+1; j < k && pojas[j].y-pojas[i].y < d; j++)
d = min(d, rastojanje(pojas[i], pojas[j]));
return d;
}
double najblizeTacke(vector<Tacka>& tacke) {
sort(begin(tacke), end(tacke), porediX);
vector<Tacka> pojas(tacke.size());
return najblizeTacke(tacke, 0, tacke.size() - 1, pojas);
}#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <limits>
#include <cmath>
#include <utility>
using namespace std;
struct Tacka {
int x, y;
};
double rastojanje(const Tacka& t1, const Tacka& t2) {
double dx = t1.x - t2.x;
double dy = t1.y - t2.y;
return sqrt(dx*dx + dy*dy);
}
bool porediX(const Tacka& t1, const Tacka& t2) {
return t1.x < t2.x;
}
bool porediY(const Tacka& t1, const Tacka& t2) {
return t1.y < t2.y;
}
// funkcija pronalazi najblizi par tacaka u delu nizu [l, r] i
// dodatno sortira tacke unutar tog dela niza po y koordinati
double najblizeTacke(vector<Tacka>& tacke, int l, int r,
vector<Tacka>& pojas) {
// za manje od 4 tacke, grubom silom odredjujemo najblizi par
if (r - l + 1 < 4) {
// odredjujemo najblizi par
double d = numeric_limits<double>::max();
for (int i = l; i < r; i++)
for (int j = i+1; j <= r; j++)
d = min(d, rastojanje(tacke[i], tacke[j]));
// sortiramo tacke po y-koordinati
sort(next(begin(tacke), l), next(begin(tacke), r+1),
porediY);
return d;
}
// delimo niz tacaka sa pozicija [l, r] u dve polovine
int s = l + (r - l) / 2;
int x = tacke[s].x;
// rekurzivno pronalazimo najblizi par u levoj i desnoj
// polovini niza sortirajuci te polovine po y koordinati
double d1 = najblizeTacke(tacke, l, s, pojas);
double d2 = najblizeTacke(tacke, s+1, r, pojas);
// najmanje rastojanje svih parova tacaka
double d = min(d1, d2);
// objedinjavamo dva sortirane polovine
// (koristimo niz pojas kao pomocni)
merge(next(begin(tacke), l), next(begin(tacke), s+1),
next(begin(tacke), s+1), next(begin(tacke), r+1),
begin(pojas), porediY);
copy(begin(pojas), next(begin(pojas), r-l+1),
next(begin(tacke), l));
// pronalazimo tacke u pojasu sirine 2d oko sredisnje linije
int k = 0;
double dl = x - d, dr = x + d;
for (int i = l; i <= r; i++)
if (dl <= tacke[i].x && tacke[i].x <= dr)
pojas[k++] = tacke[i];
// analiziramo sve tacke u pojasu
for (int i = 0; i < k; i++)
// svaku tacku poredimo samo sa onim tackama koje su u
// pravougaoniku iznad nje
for (int j = i+1; j < k && pojas[j].y-pojas[i].y < d; j++)
d = min(d, rastojanje(pojas[i], pojas[j]));
return d;
}
double najblizeTacke(vector<Tacka>& tacke) {
sort(begin(tacke), end(tacke), porediX);
vector<Tacka> pojas(tacke.size());
return najblizeTacke(tacke, 0, tacke.size() - 1, pojas);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
int n;
cin >> n;
vector<Tacka> tacke(n);
for (int i = 0; i < n; i++)
cin >> tacke[i].x >> tacke[i].y;
cout << fixed << showpoint << setprecision(5)
<< najblizeTacke(tacke) << endl;
return 0;
}