Pagini recente » Cod sursa (job #2921067) | Cod sursa (job #1528934) | Cod sursa (job #1167356) | Cod sursa (job #2917835) | Cod sursa (job #1419353)
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#define N 100000
#define MULT 9223372036854775807
using namespace std;
struct mazi{
long long x,y;
};
mazi v[N+1];
mazi aux[N+1];
long long dmin;
long long dist(mazi a,mazi b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
long long min(long long a,long long b){
if (a<b) return a;
return b;
}
void merge(int l1,int r1,int l2,int r2){
int k=0;
while(l1<=r1 &&l2<=r2){
k++;
if (v[l1].y<v[l2].y){
aux[k]=v[l1];
l1++;
}
else {
aux[k]=v[l2];
l2++;
}
}
while(l1<=r1){
k++;
aux[k]=v[l1];
l1++;
}
while(l2<=r2){
k++;
aux[k]=v[l2];
l2++;
}
for(int i=r2;k>0;k--,i--)
v[i]=aux[k];
}
void query(int begin,int end){
int mid,i,j;
long long d;
if (begin>=end) return ;
mid=(begin+end)/2;
d=v[mid].x;
query(begin,mid);
query(mid+1,end);
merge(begin,mid,mid+1,end);
int k=0;
for(i=begin;i<=end;i++)
if ((v[i].x-d)*(v[i].x-d)<dmin){
k++;
aux[k]=v[i];
}
for(i=1;i<k;i++)
for(j=i+1;j<=i+8 &&j<=k;j++)
dmin=min(dmin,dist(aux[i],aux[j]));
}
bool meow(mazi a,mazi b){
if (a.x<b.x) return true;
if (a.x==b.x &&a.y<b.y) return true;
return false;
}
int main(){
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int n,i;
fin>>n;
for(i=1;i<=n;i++)
fin>>v[i].x>>v[i].y;
sort(v+1,v+n+1,meow);
dmin=MULT;
query(1,n);
//fout<<dmin;
fout<<fixed<<setprecision(6)<<sqrt(1.0*dmin);
fin.close();
fout.close();
return 0;
}