Pagini recente » Cod sursa (job #2488227) | Cod sursa (job #1542799) | Cod sursa (job #1652298) | Cod sursa (job #178533) | Cod sursa (job #2489737)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <utility>
#include <cmath>
#include <iomanip>
#define MAX 2000000000
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
pair<double, double> v[100001], w[100001], x[100001];
bool comp(pair<double, double> a, pair<double, double> b)
{
return(a.first < b.first);
}
double distance(pair<double, double> a, pair<double, double> b)
{
return sqrt((a.first-b.first)*(a.first-b.first) + (a.second-b.second)*(a.second-b.second));
}
double result(int l, int r)
{
if(l >= r-1)
return MAX;
if(l == r-2)
{
if (w[l] > w[l + 1])
swap(w[l], w[l + 1]);
return distance(v[l], v[l + 1]);
}
int mid = (l+r)/2;
double best = min(result(l, mid), result(mid+1, r));
merge(w+l, w+mid, w+mid, w+r, x);
copy(w, w+(r-l), x+l);
int sze = 0;
for(int i = l; i < r; i++)
if(abs(w[i].second - v[mid].first) <= best)
x[sze++] = w[i];
for(int i = 0; i < sze-1; i++)
for (int j = i + 1; j < sze && j - i < 8; j++)
best = min(best, distance(x[i], x[j]));
return best;
}
int main()
{
int n;
in >> n;
for(int i = 0; i < n; i++)
in >> v[i].first >> v[i].second;
sort(v, v+n);
for(int i = 0; i < n; i++)
{
w[i].first = v[i].first;
w[i].second = v[i].second;
}
out << setprecision(8) << result(0, n-1);
return 0;
}