Pagini recente » Cod sursa (job #131242) | Autentificare | Cod sursa (job #1963496) | Cod sursa (job #3130131) | Cod sursa (job #1525531)
#include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#define punct pair<double, double>
#define x first
#define y second
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
double sol,d,dist(punct,punct),X,Y;
punct p;
int n,k;
vector<punct > V;
set<punct > M;
int main()
{
f>>n;
for(;n;n--)
{
f>>X>>Y;
V.push_back(make_pair(X,Y));
}
sort(V.begin(),V.end());
sol = 2000000000.0*sqrt(2);
for(auto it:V)
{
while(it.x-V[k].x>=sol)
{
M.erase(make_pair(V[k].y,V[k].x));
k++;
}
p=make_pair(it.y,it.x);
set<punct >::iterator j;
j=M.lower_bound(make_pair(p.x-sol,p.y-sol));
for(;j!=M.end()&&j->x<=p.x+sol;j++)
{
d=dist(p,*j);
sol=min(sol,d);
}
M.insert(p);
}
g<<fixed<<setprecision(10)<<sol;
return 0;
}
double dist(punct A, punct B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}