Pagini recente » Cod sursa (job #2086760) | Cod sursa (job #800539) | Cod sursa (job #825245) | Cod sursa (job #1442504) | Cod sursa (job #1553435)
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
#define MAX 100005
#define pdd pair<double,double>
#define x first
#define y second
using namespace std;
int n;
pdd l[MAX];
double dist2(pdd a, pdd b){
return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
double dist(int s, int d){
if(d - s == 2)
return dist2(l[s], l[s + 1]);
if(d - s == 3){
double d1 = dist2(l[s], l[s + 1]);
double d2 = dist2(l[s + 1], l[s + 2]);
double d3 = dist2(l[s], l[s + 2]);
double min = d1 < d2 ? d1 : d2;
return min < d3 ? min : d3;
}
double xdr = l[(s + d) / 2].x;
double r1 = dist(s, (s + d) / 2);
double r2 = dist((s + d) / 2, d);
double r = r1 < r2 ? r1 : r2;
double rez = r;
vector<pdd> Y;
int poz = (s + d) / 2;
while(poz >= s && xdr - l[poz].x <= r)
poz--;
poz++;
while(poz < d && l[poz].x - xdr <= r)
Y.push_back(l[poz++]);
for(int i = 0; i < Y.size(); i++){
if(Y[i].x > xdr)
break;
for(int j = i + 1; j < i + 8 && j < Y.size(); j++){
double aux = dist2(Y[i], Y[j]);
rez = aux < rez ? aux : rez;
}
}
return rez;
}
int main(){
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%lf%lf", &l[i].x, &l[i].y);
sort(l, l + n);
printf("%lf\n", dist(0, n));
return 0;
}