Cod sursa(job #792145)

Utilizator RaileanuCristian Raileanu Raileanu Data 26 septembrie 2012 16:31:38
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include<fstream>
#include<math.h>


using namespace std;

#define MAXN 50000
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;
        }