Pagini recente » Cod sursa (job #2071489) | Istoria paginii utilizator/horatiuros | Cod sursa (job #164076) | Istoria paginii runda/concurs1/clasament | Cod sursa (job #2005792)
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <fstream>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
#define int long long
int n,k,a,b;
double dminr;
double dist(pair <int, int> A, pair <int, int> B)
{
double d;
long long v;
v=((long long)(A.first-B.second)*(long long)(A.first-B.second)+(long long)(A.second-B.first)*(long long)(A.second-B.first));
d=sqrt((double)v);
return d;
}
vector <pair <int, int> > PX;
set <pair <int, int> > SY;
set <pair <int, int> > :: iterator it,cit;
#undef int
int main()
{
#define int long long
fin>>n;
for (int i=1;i<=n;i++)
{
long long x,y;
fin>>x>>y;
PX.push_back(make_pair(x,y));
}
sort(PX.begin(),PX.end());
dminr=10000000.0;
k=0;
SY.insert(make_pair(PX[0].second,PX[0].first));
for (int i=1;i<n;i++)
{
/// unele puncte prea departate pot fi sterse din SY si trecut de ele in PX
while (1)
{
if (k==i)
break;
if (PX[i].first-PX[k].first>dminr)
{
SY.erase(make_pair(PX[k].second,PX[k].first));
k++;
}
else
break;
}
/// trebuie obtinute punctele din SY care sunt la departare <= dminr pe oY
SY.insert(make_pair(PX[i].second,PX[i].first));
it=SY.lower_bound(make_pair(PX[i].second,PX[i].first));
cit=it;
/// 4 puncte situate in jos
if (cit!=SY.begin())
{
cit--;
if (dist(PX[i],*cit)<dminr)
{
dminr=dist(PX[i],*cit);
}
}
if (cit!=SY.begin())
{
cit--;
if (dist(PX[i],*cit)<dminr)
{
dminr=dist(PX[i],*cit);
}
}
if (cit!=SY.begin())
{
cit--;
if (dist(PX[i],*cit)<dminr)
{
dminr=dist(PX[i],*cit);
}
}
if (cit!=SY.begin())
{
cit--;
if (dist(PX[i],*cit)<dminr)
{
dminr=dist(PX[i],*cit);
}
}
/// 4 puncte situate in sus
cit=it;
cit++;
if (cit!=SY.end())
if (dist(PX[i],*cit)<dminr)
{
dminr=dist(PX[i],*cit);
cit++;
}
if (cit!=SY.end())
if (dist(PX[i],*cit)<dminr)
{
dminr=dist(PX[i],*cit);
cit++;
}
if (cit!=SY.end())
if (dist(PX[i],*cit)<dminr)
{
dminr=dist(PX[i],*cit);
cit++;
}
if (cit!=SY.end())
if (dist(PX[i],*cit)<dminr)
{
dminr=dist(PX[i],*cit);
cit++;
}
}
fout<<setprecision(6)<<fixed<<dminr;
return 0;
}