Pagini recente » Cod sursa (job #5589) | Cod sursa (job #1252053) | Cod sursa (job #1125433) | Cod sursa (job #3222476) | Cod sursa (job #792146)
Cod sursa(job #792146)
#include<fstream>
#include<math.h>
using namespace std;
#define MAXN 100100
int n, nrc, a[800][800], st[MAXN],i,x[MAXN], y[MAXN];
double dx,dy,xmin,ymin,xmax, ymax, dmin;
int ultim(int nod) {
while (st[nod])
nod=st[nod];
return nod;}
void parcurg(int nod){
double d;
do
{d=sqrt(pow(x[i]-x[nod],2)+pow(y[i]-y[nod],2) );
if (d<dmin && nod!=i) dmin=d;
nod=st[nod];}
while (st[nod]); }
int main(){
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
scanf("%i",&n);
for (i=1; i<=n; i++)
scanf("%i %i",x[i],y[i]);
nrc=sqrt(n)+1;
ymin=ymax=y[1];
xmin=xmax=x[1];
for (i=1;i<=n; i++)
{ if (x[i]>xmax) xmax=x[i];
else if (x[i]<xmin) xmin=x[i];
if (y[i]>ymax) ymax=y[i];
else if (y[i]<ymin) ymin=y[i]; };
dx=(xmax-xmin)/nrc;
dy=(ymax-ymin)/nrc;
for (i=1; i<=n; i++)
{ int zonax= (x[i]-xmin)/dx+1;
int zonay= (y[i]-ymin)/dy+1;
if (a[zonax][zonay] ==0) a[zonax][zonay]=i;
else st[ultim(a[zonax][zonay])]=i; };
int j,k;
dmin=sqrt(pow(x[1]-x[2],2)+pow(y[1]-y[2],2));
for (i=1; i<=n; i++)
for (j=(x[i]-xmin)/dx; j<=(x[i]-xmin)/dx+2; j++)
for (k=(y[i]-ymin)/dx; k<=(y[i]-ymin)/dy+2; k++)
if (a[j][k]) parcurg(a[j][k]);
printf("%lf\n", dmin);
return 0;
}