Pagini recente » Cod sursa (job #506001) | Cod sursa (job #2979629) | Cod sursa (job #2942828) | Cod sursa (job #1826978) | Cod sursa (job #2978295)
#include <bits/stdc++.h>
#define punct pair<int,int>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
punct v[100010];
set<punct>M;
int i, n, a, b, k;
double d, dist(punct, punct);
int main()
{
f >> n;
for (i = 0; i < n; i++)
{
f >> a >> b;
v[i] = make_pair(a, b);
}
sort(v, v + n);
d = 2000000001.0 * sqrt(2.0);
M.insert(make_pair(v[0].second, v[0].first));
for (i = 1; i < n; i++)
{
for (; (double)(v[i].first - v[k].first) > d; k++)
M.erase(make_pair(v[k].second, v[k].first));
punct P = make_pair(v[i].second, v[i].first);
set<punct>::iterator
is = M.lower_bound(make_pair((int)(P.first - d - 1), -1000000001));
for (; is != M.end() && (double)(is->first - P.first) <= d; is++)
d = min(d, dist(*is, P));
M.insert(P);
}
g << fixed << setprecision(10) << d;
return 0;
}
double dist(punct A, punct B)
{
double
xa = (double)A.first,
xb = (double)B.first,
ya = (double)A.second,
yb = (double)B.second;
return sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
}