Pagini recente » Cod sursa (job #2378769) | Cod sursa (job #207854) | Cod sursa (job #330145) | Autentificare | Cod sursa (job #1534045)
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <iostream>
#define x first
#define y second
using namespace std;
const int MAXN = 100005;
const double MAXER = 1e-6;
const char iname[] = "cmap.in",
oname[] = "cmap.out";
int n;
pair<int, int> sortx[MAXN], sorty[MAXN];
inline long double min(long double d1, long double d2){
if(d1 < d2)
return d1;
return d2;
}
bool cmp(pair<int, int> a, pair<int, int> b){
if(a.y < b.y)
return true;
if(a.y == b.y && a.x <= b.x)
return true;
return false;
}
double calcDist(pair<int, int> a, pair<int, int> b){
return sqrt((int64_t)a.x*a.x + (int64_t)b.x*b.x - (int64_t)2*a.x*b.x +(int64_t)a.y*a.y + (int64_t)b.y*b.y - (int64_t)2*a.y*b.y);
}
long double getD(int lo, int hi){
if(hi - lo <= 2){
long double dmin = INFINITY, d;
for(int i = lo; i <= hi; ++i){
for(int j = i+1; j <= hi; ++j){
d = calcDist(sortx[i], sortx[j]);
if(d < dmin)
dmin = d;
}
}
return dmin;
}
int mid = (lo+hi)/2;
long double d1 = getD(lo, mid);
long double d2 = getD(mid+1, hi);
long double d = min(d1, d2);
int centru = sortx[mid].x;
int beg = -1, end = -1;
for(int i = lo; i <= hi; ++i){
if(sortx[i].x >= centru - d && sortx[i].x <= centru + d)
if(beg == -1)
beg = i;
else
end = i;
}
if(beg != -1 && end != -1){
sort(sortx+beg, sortx+end, cmp);
for(int i = beg; i < end; ++i){
int j;
for(j = i+1; j <= i+7 && j < end; ++j){
d1 = calcDist(sortx[i], sortx[j]);
if(d1 < d)
d = d1;
}
i = j - 1;
}
}
return d;
}
int main()
{
freopen(iname, "r", stdin);
freopen(oname, "w", stdout);
scanf("%d", &n);
int a,b;
for(int i = 0; i < n; ++i){
scanf("%d %d", &a, &b);
sortx[i] = make_pair(a,b);
sorty[i] = make_pair(a,b);
}
sort(sortx, sortx+n);
sort(sorty, sorty+n, cmp);
double ans = getD(0, n-1);
cout << fixed;
cout << setprecision(7) << ans;
return 0;
}