Pagini recente » Cod sursa (job #815684) | Borderou de evaluare (job #243018) | Borderou de evaluare (job #1514462) | Borderou de evaluare (job #2689570) | Cod sursa (job #1674699)
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
struct nod
{
long long x,y;
};
#define DIM 10000
char buff[DIM];
int poz=0;
void citeste(long long &numar)
{
numar = 0;
char semn='+';
while (buff[poz] < '0' || buff[poz] > '9')
{
semn = buff[poz];
if (++poz == DIM)
fread(buff,1,DIM,stdin),poz=0;
}
while ('0'<=buff[poz] && buff[poz]<='9')
{
numar = numar*10 + buff[poz] - '0';
if (++poz == DIM)
fread(buff,1,DIM,stdin),poz=0;
}
if (semn == '-')
numar = -numar;
}
long long n;
inline bool compare(nod a,nod b)
{
if(a.x!=b.x)
return a.x<b.x;
return a.y<b.y;
}
inline bool comp(nod a,nod b)
{
if(a.y!=b.y)
return a.y<b.y;
return a.x<b.x;
}
nod v[100010],C[100010];
double dist(int s,int d)
{
if(d-s>3)
{
double mn=min(dist(s,(s+d)/2),dist((s+d)/2,d));
int k=0,ls,ld,i;
double c=(v[(s+d)/2].x+v[(s+d)/2-1].x)/2;
i=(s+d)/2-1;
while(c-v[i].x<=mn && i>=s)
C[k++]=v[i--];
i=(s+d)/2;
while(v[i].x-c<=mn && i<d)
C[k++]=v[i++];
sort(C,C+k,comp);
int j;
double x;
for(i=ls;i<k-1;++i)
for(j=i+1;j<i+8 && j<k;++j)
mn=min(mn,sqrt(( C[j].x - C[i].x ) * ( C[j].x - C[i].x ) + ( C[j].y - C[i].y ) * ( C[j].y - C[i].y )));
return mn;
}
else
{
double mn=1e9;
int i,j;
for(i=s;i<d-1;++i)
for(j=i+1;j<d;++j)
mn=min(mn,sqrt(( v[i].x - v[j].x ) * ( v[i].x - v[j].x ) + ( v[i].y - v[j].y ) * ( v[i].y - v[j].y ) ) );
return mn;
}
}
int main()
{
freopen("cmap.in","r",stdin);
freopen("cmap.out","w",stdout);
int i;
citeste(n);
for(i=0;i<n;++i)
{
citeste(v[i].x);
citeste(v[i].y);
C[i]=v[i];
}
sort(v,v+n,compare);
double x=(dist(0,n));
printf("%lf",x);
}