Cod sursa(job #613282)

Utilizator morlockRadu Tatomir morlock Data 20 septembrie 2011 18:20:11
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.74 kb
#include <iostream>
#include <fstream>
#include <math.h>

#define swap(a,b) aux=a; a=b; b=aux;

using namespace std;

double x[100], y[100], aux;
int i, n, v;

ifstream in("cmap.in");
ofstream out("cmap.out");

void sort(int n)
{ int m=0, nr=0;

  while (m==0)
   {
       m=1;
       nr++;
       for (i=1; i<=(n-nr); ++i)
        {
            if ( x[i] > x[i+1] )
             {
                 swap(x[i], x[i+1]);
                 swap(y[i], y[i+1]);
                 m=0;
             }
        }
   }


}

double distanta(int i)
{ double dist;

    dist = sqrt ( (x[i]-x[i+1])*(x[i]-x[i+1]) + (y[i]-y[i+1])*(y[i]-y[i+1]) );

    return dist;
}

int main()
{ double ds, dd, d, dm;
  int a, b, lim=0;
    in>>n;

    for (i=1; i<=n; ++i)
     in>>x[i]>>y[i];

    sort(n);

    ds = distanta(1);

    for (i=2; i<n/2; ++i)
     {
         if ( fabs( y[i] - y[i+1] ) < ds )
          ds = distanta(i);
     }


    dd = distanta(n/2);

    for (i=n/2; i<n; ++i)
     {
         if ( fabs( y[i] - y[i+1] ) < dd )
         dd = distanta(i);
     }


     dm = min (dd,ds);


     if ( n % 2 == 0 ) v = (x[n/2] + x[n/2 + 1]) / 2;
      else v = x[n/2];

      a = n/2;

      while ( lim == 0 )
       {
           lim = 1;
           if ( v - x[a] <= dm )
            {
                --a;
                lim = 0;
            }
       }

       b=n/2+1;
       lim=0;

       while ( lim == 0 )
       {
           lim = 1;
           if ( x[b] - v <= dm )
            {
                ++b;
                lim = 0;
            }
       }


   for (i=a; i<=b; ++i)
      if ( fabs( y[i] - y[i+1] ) < dm )
          dm = distanta(i);



  out<<dm;


return 0;
}