Pagini recente » Cod sursa (job #3290713) | Cod sursa (job #19381) | Cod sursa (job #2150737) | Cod sursa (job #2918674) | Cod sursa (job #2818484)
#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
#define x first
#define y second
#define point pair<long long, long long>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
vector<point> xs, ys, zs;
int n;
void read()
{
f>>n;
long long x, y;
for(int i = 1;i <= n;++i)
f>>x>>y, xs.push_back(make_pair(x, y));
sort(xs.begin(), xs.end());
for(point punct : xs)
ys.push_back(make_pair(punct.y, punct.x));
}
long long distance(point p1, point p2)
{
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
long long compute(long long left, long long right)
{
if(left >= right)
return oo;
if(right - left == 1)
return distance(xs[left], xs[right]);
long long mid = (left + right) >> 1;
long long best = min(compute(left, mid), compute(mid, right));
sort(ys.begin() + left, ys.begin() + right);
zs.clear();
for(int i = left;i < right;++i)
if(abs(ys[i].y - xs[mid].x) <= best)
zs.push_back(ys[i]);
for(int i = 0;i < zs.size() - 1;++i)
for(int j = i + 1;j < zs.size() && j - i < 8;++j)
best = min(best, distance(zs[i], zs[j]));
return best;
}
void solve()
{
g<<setprecision(6)<<fixed<<sqrt(compute(0, n));
}
int main()
{
read();
solve();
return 0;
}