Pagini recente » Cod sursa (job #2019371) | Cod sursa (job #185246) | Cod sursa (job #2735244) | Cod sursa (job #914075) | Cod sursa (job #2472721)
#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], x[100001];
bool comp(pair<double, double> a, pair<double, double> b)
{
if(a.first > b.first)
return 0;
return 1;
}
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)
return min(distance(v[l], v[l+1]), distance(v[l+1], v[r]));
int mid = (l+r)/2;
double best = min(result(l, mid), result(mid+1, r));
int sze = 0;
for(int i = l; i < r; i++)
if(v[i].second - v[mid].first <= best)
x[sze++] = v[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, comp);
out << setprecision(8) << result(0, n-1);
return 0;
}