Pagini recente » Cod sursa (job #40152) | Cod sursa (job #2856235) | Cod sursa (job #965106) | Diferente pentru implica-te/arhiva-educationala intre reviziile 145 si 144 | Cod sursa (job #1730294)
#include<cstdio>
#include <algorithm>
#include <cmath>
#define x first
#define y second
#define mkp make_pair
#define ll long long
#define inf 900000000000000000
using namespace std;
FILE*si=fopen("cmap.in","r");
FILE*so=fopen("cmap.out","w");
pair<int,int> v[100005],aux[100005];
bool cmp(pair<int,int> a,pair<int,int> b)
{
if(a.y<b.y)
return true;
if(a.y==b.y)
if(a.x<b.x)
return true;
return false;
}
ll dist(pair<int,int> a,pair<int,int> b)
{
return 1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y);
}
long long rez(int st,int dr)
{
if(st==dr)
return inf;
if(st+1==dr)
{
return dist(v[st],v[dr]);
}
int mid=(st+dr)/2,midx=v[mid].x;
long long sol=min(rez(st,mid),rez(mid+1,dr));
merge(v+st,v+mid+1,v+mid+1,v+dr+1,aux+1,cmp);
int n=dr-st+1;
for(int i=1;i<=n;++i)
{
v[st+i-1]=aux[i];
}
n=1;
for(int i=st;i<=dr;++i)
{
if(1LL*abs(v[i].x-midx)*abs(v[i].x-midx)<=sol)
aux[n++]=v[i];
}
for(int i=1;i<n;++i)
{
for(int j=i+1;j<n;++j)
{
if(1LL*abs(v[i].y-v[j].y)*abs(v[i].y-v[j].y)<=sol)
sol=min(sol,dist(v[i],v[j]));
}
}
return sol;
}
int main()
{
int n;
fscanf(si,"%i",&n);
int i,a,b;
for(i=1;i<=n;i++)
{
fscanf(si,"%i %i",&a,&b);
v[i]=mkp(a,b);
}
sort(v+1,v+1+n);
fprintf(so,"%.6f",sqrt(rez(1,n)));
return 0;
}