Pagini recente » Cod sursa (job #2055709) | Cod sursa (job #2134188) | Cod sursa (job #1958544) | Cod sursa (job #979088) | Cod sursa (job #2971912)
#include<fstream>
#include<algorithm>
#include<set>
#include<cmath>
#include<deque>
#include<iomanip>
#include<iostream>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
struct ura
{
int x, y;
bool operator<(const ura& rhs) const
{
if(y == rhs.y)
return x < rhs.x;
return y < rhs.y;
}
} v[100001];
set<ura> s;
deque<set<ura>::iterator> d;
bool cmp(ura a, ura b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
double dist(ura a, ura b)
{
uint64_t dist2 = (a.x-b.x) * (a.x-b.x) + (a.y-b.y)*(a.y-b.y);
return sqrt(dist2);
}
int main()
{
int n;
in>>n;
for(int i=1; i<=n; i++)
{
int x, y;
in>>x>>y;
v[i] = {x, y};
}
sort(v+1, v+n+1, cmp);
double dmin = 1e9;
for(int i=1; i<=n; i++)
{
auto it = s.lower_bound({0, v[i].y-dmin-1});
while((*it).y <= v[i].y + dmin + 1 && it != s.end())
{
if((*it).x < v[i].x - dmin - 1)
d.push_back(it);
else
dmin = min(dmin, dist(*it, v[i]));
++it;
}
for(auto it1 : d)
{
s.erase(it1);
d.pop_front();
}
s.insert(v[i]);
}
out<<fixed<<setprecision(6)<<dmin;
return 0;
}