Pagini recente » Cod sursa (job #1846479) | Cod sursa (job #2442820) | Cod sursa (job #2852197) | Cod sursa (job #2414630) | Cod sursa (job #3223037)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>
using namespace std;
#define int long long
ifstream in("cmap.in");
ofstream out("cmap.out");
int n;
pair<int, int> v[100005];
pair<int, int> w[100005];
int INF = 4e18;
int dist(pair<int, int> a, pair<int, int> b)
{
return ((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
if(a.second == b.second)
{
return a.first < b.first;
}
return a.second < b.second;
}
int solve(int st, int dr)
{
if(st == dr)
{
return INF;
}
int mij = (st + dr) / 2;
int d1 = solve(st, mij);
int d2 = solve(mij + 1, dr);
int dmin = min(d1, d2);
int cnt = 0;
int distanta;
for(int i = st; i<=dr; i++)
{
distanta = abs(v[i].first - v[mij].first) * abs(v[i].first - v[mij].first);
if(distanta <= dmin)
{
cnt++;
w[cnt] = v[i];
}
}
sort(w+1, w+cnt+1, cmp);
for(int i = 1; i<=cnt; i++)
{
for(int j = i + 1; j<=cnt && dist(w[i], w[j]) <= dmin; j++)
{
dmin = min(dmin, dist(w[i], w[j]));
}
}
return dmin;
}
signed 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<<sqrt(solve(1, n));
return 0;
}