Pagini recente » Cod sursa (job #1331037) | Cod sursa (job #3037558) | Cod sursa (job #2124783) | Cod sursa (job #2838541) | Cod sursa (job #432318)
Cod sursa(job #432318)
#include <algorithm>
#include <cmath>
using namespace std;
#define INF 100000000000000000LL
#define DIM 100005
struct punct {long long x,y;} v[DIM],a[DIM];
int n,m;
void read ()
{
int i;
scanf ("%d",&n);
for (i=1; i<=n; ++i)
scanf ("%lld%lld",&v[i].x,&v[i].y);
}
struct cmp1
{
bool operator () (const punct &a,const punct &b) const
{
return a.x<b.x;
}
};
struct cmp2
{
bool operator () (const punct &a,const punct &b) const
{
return a.y<b.y;
}
};
inline double dist (punct a,punct b)
{
return sqrt ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
inline int cbin (punct p,double dmin)
{
int st,dr,mij,sol;
for (st=1, sol=dr=m; st<=dr; )
{
mij=(st+dr)/2;
if (p.y-dmin<=a[mij].y)
{
dr=mij-1;
sol=mij;
}
else
st=mij+1;
}
return sol;
}
double calc (int st,int dr)
{
double dmin,d;
int mij,i,j;
if (st>=dr)
return INF;
if (st+1==dr)
return dist (v[st],v[dr]);
mij=(st+dr)/2;
d=dmin=min (calc (st,mij),calc (mij+1,dr));
for (m=0, i=mij+1; v[i].x<=v[mij].x+dmin && i<=dr; ++i)
a[++m]=v[i];
sort (a+1,a+m+1,cmp2 ());
for (i=st; i<=mij; ++i)
for (j=cbin (v[i],dmin); j<=m && v[i].y-dmin<=a[j].y && a[j].y<=v[i].y+dmin; ++j)
d=min (d,dist (v[i],a[j]));
return d;
}
int main ()
{
freopen ("cmap.in","r",stdin);
freopen ("cmap.out","w",stdout);
read ();
sort (v+1,v+n+1,cmp1 ());
printf ("%lf",calc (1,n));
return 0;
}