Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | cmap.in, cmap.out | Sursă | Arhiva educationala |
| Autor | Arhiva Educationala | Adăugată de |  Coroian David •Coroian_David |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Cele mai apropiate puncte din plan
Se dau N puncte în plan cu coordonate numere întregi. Sa se determine distanta intre cele mai apropiate 2 puncte.
Date de intrare
Fişierul de intrare cmap.in conţine pe prima linie un număr N, cu semnificaţia din enunţ. Pe următoarele N linii se vor afla doua numere Xi şi Yi, coordonatele celui de-al i-lea punct.
Date de ieşire
În fişierul de ieşire cmap.out se va afişa distanta intre cele mai apropiate 2 puncte.
Restricţii
- 1 ≤ N ≤ 100 000
- -1 000 000 000 ≤ Xi ≤ 1 000 000 000
- -1 000 000 000 ≤ Yi ≤ 1 000 000 000
- Oricare doua puncte sunt distincte.
- Pentru 20% din teste 1 ≤ N ≤ 1 000
Exemplu
| cmap.in | cmap.out |
|---|---|
| 10 26 77 12 37 14 18 19 96 71 95 91 9 98 43 66 77 2 75 94 91 | 18.681542 |
Indicaţii de rezolvare
O soluţie brute-force de complexitate O(N*N) obţine 20 de puncte.
O alta soluţie de complexitate O(N*N*log2N) sortează numerele crescător după abscisa şi apoi foloseşte un algoritm divide et impera. Se împart cele N puncte în doua grupuri st şi dr, se calculează st_min şi dr_min, distanta intre cele mai apropiate puncte din grupul st şi dr, apoi se calculează st_dr_min, distanta intre cele mai apropiate 2 puncte, unul aparţinând grupului st şi altul lui dr. Distanta intre cele mai apropiate puncte o sa fie minim(st_min, dr_min, st_dr_min).
Se observa ca cea mai costisitoare operaţie este cea la care se calculează st_dr_min. Aceasta se poate reduce de la O(N*N) la O(N) folosind următoarea observaţie: notam cu dist minimul dintre st_min si dr_min. Pentru orice punct P din grupul st este suficient sa ne uitam la punctele din dreptunghiul cu laturile dist si 2*dist din grupul dr ca in figura.
Se observa ca în dreptunghi sunt maxim 6 astfel de puncte, deci complexitatea se reduce de la O(N*N) la O(6*N), astfel complexitatea finala devenind O(N*log2N). Aceasta soluţie foloseşte ideea prezentata mai sus şi obţine 100 de puncte.
