Pagini recente » Cod sursa (job #710944) | Cod sursa (job #1273448) | Cod sursa (job #311916) | Cod sursa (job #1347814) | Cod sursa (job #3217843)
#include <bits/stdc++.h>
#define MAX 100005
#define inf 2e9
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct point
{
double x,y;
}pct[MAX],v[MAX];
bool crt1(point a,point b)
{
return a.x<b.x;
}
bool crt2(point a,point b)
{
return a.y<b.y;
}
double dist(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
double divide(int st,int dr)
{
if(dr-st<3)
{
double rez=inf;
int i,j;
for(i=st;i<dr;++i)
for(j=i+1;j<=dr;++j)
rez=min(rez,dist(pct[i],pct[j]));
return rez;
}
else
{
int mij=(st+dr)/2;
double rez1=divide(st,mij);
double rez2=divide(mij+1,dr);
double rez=min(rez1,rez2);
int ind=0;
int i;
for(i=st;i<=dr;++i)
if(fabs(pct[i].x-pct[mij].x)<=rez)
v[++ind]=pct[i];
sort(v+1,v+ind+1,crt2);
int j;
for(i=1;i<ind;++i)
for(j=1;j<8;++j)
rez=min(rez,dist(v[i],v[i+j]));
return rez;
}
}
int main()
{
int n;
fin>>n;
int i;
for(i=1;i<=n;++i)
fin>>pct[i].x>>pct[i].y;
sort(pct+1,pct+n+1,crt1);
fout<<fixed<<setprecision(10)<<divide(1,n);
return 0;
}