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
Paul: Nu sunt consitente notatiile. Cand apare (p1, p2), (q1, q2), cand apare (x, y). Cred ca notatia cu (x, y) e mai naturala.
Considerăm un plan euclidian ce conţine n puncte date prin coordonatele lor. În acest plan, dacă 
iar 
, atunci distanţa dintre aceste două puncte este: 
.
Cerinţă
Să se determine distanţa între cele mai apropiate două 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 câte două numere xi şi yi, separate printr-un spaţiu, semnificând coordonatele celui de al i-lea punct.
Date de ieşire
În fişierul de ieşire cmap.out se va afişa distanţa dintre cele mai apropiate două puncte din planul euclidian.
Restricţii
- 1 ≤ n ≤ 100 000.
- -109 ≤ xi ≤ 109.
- -109 ≤ yi ≤ 109.
- Oricare două puncte sunt distincte.
- Orice număr se găseşte la coordonate numere întregi.
- 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 ce consideră fiecare pereche de puncte are complexitatea O(N2) şi 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.
