Cod sursa(job #1313432)

Utilizator RaileanuCristian Raileanu Raileanu Data 10 ianuarie 2015 17:38:02
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.38 kb
#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;
}