Pagini recente » Borderou de evaluare (job #2691328) | Rezultatele filtrării | Cod sursa (job #23641) | Rezultatele filtrării | Cod sursa (job #2071241)
#include <cstdio>
#include <algorithm>
#include <limits.h>
#include <math.h>
#include <vector>
using namespace std;
struct punct {
long long x, y;
};
vector <punct> v;
long long dist(punct a, punct b) {
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
bool functia_de_comparare(punct a, punct b) {
if(a.x < b.x)
return true;
if(a.x > b.x)
return false;
return a.y < b.y;
}
bool functia_de_comparare2(punct a, punct b) {
return a.y < b.y;
}
long long solutie(int inceput, int sfarsit) {
if(sfarsit - inceput == 1) {
return dist(v[inceput], v[sfarsit]);
}
if(sfarsit - inceput == 2) {
return min(dist(v[inceput], v[sfarsit]), min(dist(v[inceput + 1], v[sfarsit]), dist(v[inceput], v[inceput + 1])));
}
int mediana = (inceput + sfarsit) / 2;
long long distanta_minima = min(solutie(inceput, mediana), solutie(mediana + 1, sfarsit));
vector <punct> auxiliar;
for (int i = inceput; i <= sfarsit; i ++)
if ((v[i].x - v[mediana].x) * (v[i].x - v[mediana].x) <= distanta_minima)
auxiliar.push_back(v[i]);
sort(auxiliar.begin(), auxiliar.end(), functia_de_comparare2);
for (int i = 0; i < auxiliar.size(); i++)
for (int j = i + 1; j <= i + 7 && j < auxiliar.size(); j++)
distanta_minima = min(distanta_minima, dist(auxiliar[i], auxiliar[j]));
return distanta_minima;
}
int main() {
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
int n;
scanf("%d", &n);
v.reserve(n + 2);
for (int i = 0; i < n; i++)
scanf("%d %d", &v[i].x, &v[i].y);
sort(v.begin(), v.end(), functia_de_comparare);
double distanta = sqrt(solutie(0, n-1));
printf("%.6lf\n", distanta);
return 0;
}