Pagini recente » Cod sursa (job #2750049) | Cod sursa (job #554081) | Cod sursa (job #2889482) | Cod sursa (job #1676845) | Cod sursa (job #3223033)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
int n;
pair<int, int> v[100005];
pair<int, int> w[100005];
int INF = 2e9;
long double dist(pair<int, int> a, pair<int, int> b)
{
return (long double)(sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second)));
}
long double solve(int st, int dr)
{
if(st == dr)
{
return INF;
}
int mij = (st + dr) / 2;
long double d1 = solve(st, mij);
long double d2 = solve(mij + 1, dr);
long double dmin = min(d1, d2);
int cnt = 0;
for(int i = st; i<=dr; i++)
{
if(abs(v[i].first - v[mij].first) <= dmin)
{
cnt++;
w[cnt] = v[i];
}
}
for(int i = 1; i<=cnt; i++)
{
for(int j = i + 1; j<=cnt; j++)
{
dmin = min(dmin, dist(w[i], w[j]));
}
}
return dmin;
}
int main()
{
in>>n;
for(int i = 1; i<=n; i++)
{
in>>v[i].first>>v[i].second;
}
sort(v+1, v+n+1);
out<<setprecision(6)<<fixed<<solve(1, n);
return 0;
}