Pagini recente » Cod sursa (job #2525580) | Cod sursa (job #685993) | Cod sursa (job #1111808) | Cod sursa (job #1007221) | Cod sursa (job #700724)
Cod sursa(job #700724)
#include <fstream>
#include <iomanip>
#include <cmath>
#include <set>
#include <algorithm>
using namespace std;
const char InFile[]="cmap.in";
const char OutFile[]="cmap.out";
const int MaxN=100111;
const double DINF=1e64;
ifstream fin(InFile);
ofstream fout(OutFile);
struct Point
{
Point(int x=0, int y=0):x(x),y(y){}
int x,y;
};
struct Point_cmp
{
inline bool operator() (const Point &a, const Point &b)
{
if(a.x==b.x)
{
return a.y<b.y;
}
return a.x<b.x;
}
};
struct Point_cmp2
{
inline bool operator() (const Point &a, const Point &b)
{
if(a.y==b.y)
{
return a.x<b.x;
}
return a.y<b.y;
}
};
inline double dist(const Point &A, const Point &B)
{
double dx=(double)(A.x)-(double)(B.x);
double dy=(double)(A.y)-(double)(B.y);
return sqrt(dx*dx+dy*dy);
}
set<Point,Point_cmp2> H;
int N;
double sol;
Point P[MaxN];
int main()
{
fin>>N;
for(register int i=1;i<=N;++i)
{
fin>>P[i].x>>P[i].y;
}
fin.close();
sort(P+1,P+1+N,Point_cmp());
int st=1;
sol=dist(P[1],P[2]);
H.insert(P[1]);
H.insert(P[2]);
for(register int i=3;i<=N;++i)
{
int x=H.size();
H.insert(P[i]);
x=H.size();
while(st<i && (double)(P[i].x-P[st].x)>sol)
{
H.erase(H.find(P[st]));
x=H.size();
++st;
}
x=H.size();
set<Point,Point_cmp2>::iterator it=H.find(P[i]);
set<Point,Point_cmp2>::iterator it2=it;
if(it!=H.begin())
{
--it;
for(register int j=1;j<=3;++j)
{
sol=min(sol,dist(*it,P[i]));
if(it==H.begin())
{
break;
}
--it;
}
}
++it2;
for(register int j=1;j<=3;++j)
{
if(it2==H.end())
{
break;
}
sol=min(sol,dist(*it2,P[i]));
++it2;
}
}
fout<<fixed<<setprecision(20)<<sol;
fout.close();
return 0;
}