Pagini recente » Cod sursa (job #218781) | Cod sursa (job #2464278) | Cod sursa (job #290500) | Cod sursa (job #2303240) | Cod sursa (job #579356)
Cod sursa(job #579356)
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
const char InFile[]="cmap.in";
const char OutFile[]="cmap.out";
const long long LLINF=1LL<<62;
const int MaxN=100111;
ifstream fin(InFile);
ofstream fout(OutFile);
struct s_point
{
s_point(long long _x=0, long long _y=0):x(_x),y(_y){}
long long x,y;
};
struct cmp
{
inline bool operator() (const s_point &a, const s_point &b)
{
return a.x<b.x;
}
};
int N,indF;
s_point P[MaxN],F[MaxN];
inline long long dist(const s_point &a, const s_point &b)
{
long long dx=a.x-b.x;
long long dy=a.y-b.y;
return dx*dx+dy*dy;
}
inline void merge(int st, int dr)
{
int m=st+((dr-st)>>1);
s_point T[MaxN];
int ind1=st;
int ind2=m+1;
int tind=st-1;
while(ind1<=m && ind2<=dr)
{
if(P[ind1].y<P[ind2].y)
{
T[++tind]=P[ind1];
++ind1;
}
else
{
T[++tind]=P[ind2];
++ind2;
}
}
while(ind1<=m)
{
T[++tind]=P[ind1];
++ind1;
}
while(ind2<=dr)
{
T[++tind]=P[ind2];
++ind2;
}
for(register int i=st;i<=dr;++i)
{
P[i]=T[i];
}
}
long long cmap(int st, int dr)
{
if(st>=dr)
{
return LLINF;
}
if(dr==st+1)
{
if(P[st].y>P[dr].y)
{
swap(P[st],P[dr]);
}
return dist(P[st],P[dr]);
}
int m=st+((dr-st)>>1);
int d=P[m].x;
long long s=min(cmap(st,m),cmap(m+1,dr));
merge(st,dr);
indF=0;
for(int i=st;i<=dr;++i)
{
if(abs(P[i].y-d)<=s)
{
F[++indF]=P[i];
}
}
for(int i=1;i<=indF;++i)
{
for(int j=1;j<=7;++j)
{
if(i+j>indF)
{
break;
}
s=min(s,dist(F[i],F[i+j]));
}
}
return s;
}
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,cmp());
fout<<setprecision(50)<<fixed<<sqrt((double)(cmap(1,N)));
fout.close();
return 0;
}