Cod sursa(job #792134)

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

using namespace std;

#define MAXN 100100
int n, nrc, a[400][400], st[MAXN],i;
double x[MAXN], y[MAXN],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(){
        ifstream f1("cmap.in");
        ofstream f2("cmap.out");
        f1>>n;
        for (i=1; i<=n; i++)
            f1>>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]);

        f2<<dmin;
        f1.close();
        f2.close();
        return 0;
        }