Pagini recente » Cod sursa (job #2200852) | Cod sursa (job #1060144) | Cod sursa (job #3033445) | Cod sursa (job #2903225) | Cod sursa (job #1534022)
#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;
vector<pair<int, int>> inBanda;
for(int i = 0; i < n; ++i)
if(sorty[i].x >= centru - d && sorty[i].x <= centru + d)
inBanda.push_back(sorty[i]);
int size = inBanda.size();
for(int i = 0; i < size; ++i){
for(int j = i+1; j <= i+7 && j < size; ++j){
d1 = calcDist(inBanda[i], inBanda[j]);
if(d1 < d)
d = d1;
}
}
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;
}