Pagini recente » Cod sursa (job #584151) | Cod sursa (job #2978929) | Cod sursa (job #2451226) | Cod sursa (job #2082206) | Cod sursa (job #1313432)
#include<math.h>
#include<stdio.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) // st pastreaza listele punctelor din datele de intrare
{
while (st[nod]) // st[i]=j daca j urmeaza dupa i in lista zonei
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; // vom imparti domeniul minim care contine toate punctele in nrc*nrc zone dreptunghiulare
// calculez xmin ,xmax, ymin si ymax
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]; };
// am calculat xmin ,xmax, ymin si ymax
dx=(xmax-xmin)/nrc; // lungimea dreptunghiurilor pe axa Ox
dy=(ymax-ymin)/nrc; // lungimea dreptunghiurilor pe axa Oy
for (i=1; i<=n; i++) // distribui punctele in cele nrc*nrc zone
{
int zonax= (x[i]-xmin)/dx+1, zonay= (y[i]-ymin)/dy+1 ;
if (a[zonax][zonay] ==0) a[zonax][zonay]=i; // daca in zona nu mai sunt puncte
else st[ultim(a[zonax][zonay])]=i; // daca sunt, il pun la coada zonei date
}
dmin= sqrt( pow(x[1]-x[2],2) + pow(y[1]-y[2],2) );
int j,k;
for (i=1; i<=n; i++) // pt orice punct
for (j=(x[i]-xmin)/dx; j<=(x[i]-xmin)/dx+2; j++) // verifica punctele din zonele adiacente
for (k=(y[i]-ymin)/dx; k<=(y[i]-ymin)/dy+2; k++) // dar si zona in care se afla
if (a[j][k])
parcurg(a[j][k]);
printf("%lf\n", dmin);
return 0;
}