Pagini recente » Cod sursa (job #893396) | Cod sursa (job #62972) | Cod sursa (job #1267284) | Cod sursa (job #837208) | Cod sursa (job #2721433)
#include <bits/stdc++.h>
#define oo 0x3f3f3f3f
#define point pair<long long, long long>
#define x first
#define y second
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
int n;
vector<point> x, y, z;
long long dist(point p1, point p2)
{
return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}
long long solve(int st, int dr)
{
if(st >= dr)
return oo;
if(dr - st == 1)
return dist(x[st], x[st + 1]);
int mid = (st + dr) >> 1;
long long best = min(solve(st, mid), solve(mid, dr));
sort(y.begin() + st, y.begin() + dr);
z.clear();
for(int i = st;i < dr;++i)
if(abs(y[i].y - x[mid].x) <= best)
z.push_back(y[i]);
for(int i = 0;i < z.size();++i)
for(int j = i + 1;j < z.size() && j - i < 8;++j)
best = min(best, dist(z[i], z[j]));
return best;
}
void Read()
{
f>>n;
long long a, b;
for(int i = 1;i <= n;++i)
f>>a>>b, x.push_back(make_pair(a, b));
sort(x.begin(), x.end());
for(auto it : x)
y.push_back(make_pair(it.y, it.x));
g<<setprecision(6)<<fixed<<sqrt(solve(0, n));
}
int main()
{
Read();
return 0;
}