Pagini recente » Cod sursa (job #2861132) | Cod sursa (job #3159738) | Cod sursa (job #1336890) | Cod sursa (job #2674718) | Cod sursa (job #2617504)
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
ifstream f ("cmap.in");
ofstream g ("cmap.out");
typedef pair <int, int> PI;
constexpr int NMAX = 1e5 + 5;
int N;
PI a[NMAX];
set <PI> R;
void Read ()
{
f >> N;
for (int i = 1; i <= N; ++i)
f >> a[i].x >> a[i].y;
sort(a+1, a+N+1);
}
double Distance (PI a, PI b)
{
return sqrt(1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y));
}
void Solve ()
{
double sol = 2e9;
int ind_Left = 1;
for (int i = 1; i <= N; ++i)
{
while (!R.empty() && a[i].x - a[ind_Left].x >= sol)
{
R.erase({a[ind_Left].y, a[ind_Left].x});
++ind_Left;
}
int y_Down = a[i].y - (int)(sol);
int y_Up = a[i].y + (int)(sol);
set <PI> :: iterator d = R.lower_bound({y_Down, 1e9});
set <PI> :: iterator u = R.lower_bound({y_Up, 1e9});
for (set <PI> :: iterator it = d; it != u; ++it)
{
PI nr = *it;
swap(nr.x, nr.y);
double ans = Distance(nr, a[i]);
sol = min(sol, ans);
}
R.insert({a[i].y, a[i].x});
}
g << setprecision(6) << fixed;
g << sol << '\n';
}
int main()
{
Read();
Solve();
return 0;
}