Pagini recente » Istoria paginii runda/nush_chare/clasament | agm-2018 | Atasamentele paginii Clasament cerculdeinfo-lectia8-kmp.z.manacher | Istoria paginii runda/wer | Cod sursa (job #1552280)
#include <fstream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define punct pair<double,double>
#define X first
#define Y second
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
vector<punct > v;
set<punct > M;
int n,i,j;
punct P;
double x,y,d;
double dist(punct A,punct B)
{
return sqrt((A.X-B.X)*(A.X-B.X)+(A.Y-B.Y)*(A.Y-B.Y));
}
int main()
{
f>>n;
for(i=1;i<=n;i++)
{
f>>x>>y;
v.push_back(make_pair(x,y));
}
sort(v.begin(),v.end());
for(i=0;i<n;i++)
{
double aux=v[i].first;v[i].first=v[i].second;v[i].second=aux;
}
d=sqrt(2.0)*2000000000.0;
M.insert(v[0]);
for(i=0,j=1;j<n;j++)
{
for(;i<j;i++)
{
if(v[j].second-v[i].second<d)
break;
M.erase(v[i]);
}
P=make_pair(v[j].first-d,v[j].second-d);
set<punct>::iterator it=M.lower_bound(P);
for(;it->first-v[j].first<d&&it!=M.end();it++)
d=min(d,dist(*it,v[j]));
M.insert(v[j]);
}
g<<fixed<<setprecision(8)<<d;
return 0;
}