Pagini recente » Istoria paginii runda/girls/clasament | Cod sursa (job #3223443) | Cod sursa (job #2561080) | Cod sursa (job #1425463) | Cod sursa (job #2504486)
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
#define x first
#define y second
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
long long n,i,j;
pair <long long,long long> v[100001],a[100001],b[100001];
long long inter(long long st,long long mid,long long dr){
long long i=st;
long long j=mid+1;
long long k=st-1;
while(i<=mid&&j<=dr)
{
if(v[i].y<v[j].y)
a[++k]=v[i++];
else
a[++k]=v[j++];
}
for(;i<=mid;i++)
a[++k]=v[i];
for(;j<=dr;j++)
a[++k]=v[j];
for(i=st;i<=dr;i++)
v[i]=a[i];
}
long long dist(pair<long long,long long> a,pair<long long,long long> b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
long long divide(long long st, long long dr){
long long sol,i,j;
if(dr-st==1){
inter(st,st,dr);
return dist(v[st],v[dr]);
}
if(dr-st==2){
inter(st,st,dr-1);
inter(st,dr-1,dr);
return min(dist(v[st],v[dr]),min(dist(v[st+1],v[st]),dist(v[st+1],v[dr])));
}
long long mid=(st+dr)/2;
sol=min(divide(st,mid),divide(mid+1,dr));
inter(st,mid,dr);
long long cnt=0;
for(i=st;i<=dr;i++){
if(abs(v[mid].x-v[i].x)<=sol){
b[++cnt]=v[i];
}
}
for(i=1;i<cnt;i++)
for(j=i+1;j<=min(cnt,i+7);j++)
sol=min(sol,dist(b[i],b[j]));
return sol;
}
int main(){
f>>n;
for(i=1;i<=n;i++)
f>>v[i].x>>v[i].y;
sort(v+1,v+n+1);
g<<setprecision(7)<<fixed<<sqrt(divide(1,n));
return 0;
}