Pagini recente » Cod sursa (job #3264750) | Cod sursa (job #2859906) | Cod sursa (job #1188493) | Cod sursa (job #216355) | Cod sursa (job #1581989)
#include <fstream>
#include <iomanip>
#include <set>
#include <utility>
#include <algorithm>
#include <cmath>
#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));
}