Pagini recente » Cod sursa (job #1665412) | Cod sursa (job #2986124) | Cod sursa (job #2107082) | Cod sursa (job #367864) | Cod sursa (job #2969835)
#include <fstream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
char buff[4096];
int pbuf=4095;
void readbuff(){
pbuf=0;fin.read(buff,4095);
}
int citire(){
int nr=0,semn=0;
if(pbuf==4095){
semn=0;readbuff();
}
while(buff[pbuf]<'0'||buff[pbuf]>'9'){
if(buff[pbuf]=='-'){
semn=1;
}
pbuf++;
if(pbuf==4095){
readbuff();
}
}
while(buff[pbuf]>='0'&&buff[pbuf]<='9'){
nr=nr*10+buff[pbuf]-'0';pbuf++;
if(pbuf==4095){
readbuff();
}
}
if(semn==1){
nr=-nr;
}
return nr;
}
int n;
struct numere{
int x,y;
}v[100005],vst[100005],vdr[100005];
bool cmp(numere a,numere b){
if(a.x!=b.x){
return a.x<b.x;
}
else{
return a.y<b.y;
}
}
double dist(numere a,numere b){
long long rez=1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
double afis=(double)sqrt(rez);
return afis;
}
bool cmp1(numere a,numere b){
return a.y<b.y;
}
double F(int a,int b){
if(b-a+1==2){
return dist(v[a],v[b]);
}
if(b-a+1==3){
return min(dist(v[a],v[a+1]),min(dist(v[a],v[b]),dist(v[a+1],v[b])));
}
int mij=(a+b)/2;
double d=min(F(a,mij),F(mij+1,b));
int lim=(int)d+1,pozst=0,pozdr=0;
for(int i=mij;i>=a;i--){
if(v[mij].x-v[i].x+1<=lim){
pozst++;vst[pozst]=v[i];
}
else{break;}
}
for(int i=mij+1;i<=b;i++){
if(v[i].x-v[mij].x+1<=lim){
pozdr++;vdr[pozdr]=v[i];
}
else{break;}
}
sort(vst+1,vst+pozst+1,cmp1);
sort(vdr+1,vdr+pozdr+1,cmp1);
int pst=1,pdr=1;
for(int i=1;i<=pozdr;i++){
int val1=vdr[i].y-lim,val2=vdr[i].y+lim;
while(pst<=pozst&&vst[pst].y<val1){
pst++;
}
while(pdr<=pozst&&vst[pdr].y<val2){
pdr++;
}
if(pst>pozst){pst--;}
if(pdr>pozst){pdr--;}
for(int j=pst;j<=pdr;j++){
if(a==63166&&b==63234){
double ceva=dist(vst[j],vdr[i]);
}
d=min(d,dist(vst[j],vdr[i]));
}
}
return d;
}
int main()
{
n=citire();
for(int i=1;i<=n;i++){
v[i].x=citire();v[i].y=citire();
}
sort(v+1,v+n+1,cmp);
double distmin=F(1,n);
long long rez=1LL*(double)distmin*1000000;
distmin=(double)rez/1000000;
fout<<fixed<<setprecision(6)<<distmin<<'\n';
return 0;
}