Pagini recente » Cod sursa (job #584352) | Cod sursa (job #2595639) | Cod sursa (job #617678) | Cod sursa (job #1370506) | Cod sursa (job #1423373)
#include <cstdio>
#include <algorithm>
FILE* in=fopen("cmap.in","r");
FILE* out=fopen("cmap.out","w");
const int SBUF=4096;
char BUF[SBUF];
int p=SBUF;
bool cif[200];
void prec()
{
for(int i='0';i<='9'; i++)
cif[i]=1;
cif['-']=1;
}
char get_char()
{
if(p==SBUF)
{
fread(BUF,SBUF,1,in);
p=0;
}
return BUF[p++];
}
int get_int()
{
char x;
int rez=0;
x=get_char();
while(!cif[x])
x=get_char();
int neg=1;
if(x=='-')
{
neg=-1;
x=get_char();
}
while(cif[x])
{
rez=rez*10+x-'0';
x=get_char();
}
return rez*neg;
}
const int Q=1000108,INF=2000000000;
int n;
struct point{
long long x,y;
void operator =(const point &alt)
{
x=alt.x;
y=alt.y;
}
} v[Q];
long long modul(long long x)
{
return x>0?x:-x;
}
unsigned long long dist(const point &a, const point &b)
{
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
point sel[Q];
void pleaca(int st, int dr, point &a, point &b)
{
if(st==dr)
{
a=v[st];
b=v[0];
return;
}
if(st==dr-1)
{
a=v[st];
b=v[dr];
if(v[dr].y<v[st].y)
{
point aux;
aux=v[st];
v[st]=v[dr];
v[dr]=aux;
}
return;
}
int md=(st+dr)/2;
point e,r;
pleaca(st,md,a,b);
pleaca(md+1,dr,e,r);
if(dist(e,r)<dist(a,b))
{
a=e;
b=r;
}
int x1=st,x2=md+1;
int nr=0;
unsigned long long eta=dist(a,b);
while(x1<=md && x2<=dr)
{
if(v[x1].y<v[x2].y)
{
if((v[x1].x-v[md].x)*(v[x1].x-v[md].x)<=eta)
{
nr++;
sel[nr]=v[x1];
}
x1++;
}
else
{
if((v[x2].x-v[md].x)*(v[x2].x-v[md].x)<=eta)
{
nr++;
sel[nr]=v[x2];
}
x2++;
}
}
while(x1<=md)
{
if((v[x1].x-v[md].x)*(v[x1].x-v[md].x)<=eta)
{
nr++;
sel[nr]=v[x1];
}
x1++;
}
while(x2<=dr)
{
if((v[x2].x-v[md].x)*(v[x2].x-v[md].x)<=eta)
{
nr++;
sel[nr]=v[x2];
}
x2++;
}
for(int i=1;i<=7;i++)
{
sel[nr+i]=v[0];
}
for(int i=1; i<=nr; i++)
{
for(int j=1; j<=7; j++)
{
if(dist(sel[i],sel[i+j])<eta)
{
a=sel[i];
b=sel[i+j];
eta=dist(sel[i],sel[i+j]);
}
}
}
nr=0;
x1=st;
x2=md+1;
while(x1<=md && x2<=dr)
{
if(v[x1].y<v[x2].y)
{
nr++;
sel[nr]=v[x1];
x1++;
}
else
{
nr++;
sel[nr]=v[x2];
x2++;
}
}
while(x1<=md)
{
nr++;
sel[nr]=v[x1];
x1++;
}
while(x2<=dr)
{
nr++;
sel[nr]=v[x2];
x2++;
}
for(int i=1; i<=nr; i++)
{
v[st+i-1]=sel[i];
}
}
bool cmp(const point &a, const point &b)
{
return a.x<b.x;
}
int main()
{
prec();
n=get_int();
int a,b;
for(int i=1; i<=n; i++)
{
a=get_int();
b=get_int();
v[i].x=a;
v[i].y=b;
// v[i].y=1LL*b*3;
}
std::sort(v+1,v+n+1,cmp);
point g,k;
v[0].x=-INF;
v[0].y=-INF;
pleaca(1,n,g,k);
unsigned long long eta=dist(g,k);
double rez=sqrt(eta);
fprintf(out,"%.9lf",rez);
return 0;
}