Cod sursa(job #756510)

Utilizator XladhenianGrigorita Vlad-Stefan Xladhenian Data 9 iunie 2012 19:34:19
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 2.57 kb

#include <fstream>
#include <iomanip>
#include <algorithm>
#include <math.h>
using namespace std;

struct TPoint;
typedef TPoint *PPoint;
struct TPoint
{
 long X,Y;
};

long N;

TPoint Puncte[100005];

int CompareX(const void *p1,const void *p2)
{
 PPoint a = (PPoint)(p1);
 PPoint b = (PPoint)(p2);
 return a->X - b->X;
}

int CompareY(const void *p1,const void *p2)
{
 PPoint a = (PPoint)(p1);
 PPoint b = (PPoint)(p2);
 return a->Y - b->Y;
}

double mind(double a,double b)
{
 if (a < b)
   {
    return a;
   }
 return b;
}

double Dist(long a,long b)
{
 double dx = (Puncte[a].X - Puncte[b].X);
 double dy = (Puncte[a].Y - Puncte[b].Y);
 return sqrt(dx * dx + dy * dy);
}

double DM3(long left,long right)
{
 long a,b;
 double dmin = 1e64;
 for (a = left;a <= right;a += 1)
  {
   for (b = a + 1;b <= right;b += 1)
    {
     dmin = mind(dmin,Dist(a,b));
    }
  }
 return dmin;
}

double DMY(long left,long right,double dmax)
{
 long a,b,c;
 double dd;
 double dmin = 1e64;
 for (a = left;a <= right;a += 1)
  {
   for (b = (a + 1),c = 0;(b <= right) && (c < 8);b += 1)
    {
     if ((Puncte[b].X - Puncte[a].X) > dmax)
       {
        break;
       }
     dd = Dist(a,b);
     if (dd < dmin)
       {
        dmin = dd;
        if (dmin < dmax)
          {
           dmax = dmin;
          }
       }
    }
  }
 return dmin;
}

double DMX(long left,long right)
{
 if ((right - left) <= 3)
   {
    return DM3(left,right);
   }
 long mid = left + ((right - left) >> 1);
 double dmin = mind(DMX(left,mid),DMX(mid + 1,right));

 long leftm,rightm;
 double midx = (Puncte[mid].Y + Puncte[mid + 1].Y) / 2;
 leftm = mid;
 rightm = mid + 1;
 while (((midx - Puncte[leftm].Y) < dmin) && (leftm > left))
  {
   leftm -= 1;
  }
 while (((Puncte[leftm].Y - midx) < dmin) && (rightm < right))
  {
   rightm += 1;
  }

 qsort(Puncte + leftm,rightm - leftm + 1,sizeof(TPoint),CompareX);

 dmin = mind(dmin,DMY(leftm,rightm,dmin));

 return dmin;
}

int main(void)
{
 fstream fin("cmap.in",ios::in);
 fstream fout("cmap.out",ios::out);
 long i;

 fin >> N;
 for (i = 0;i < N;i += 1)
  {
   fin >> Puncte[i].X >> Puncte[i].Y;
  }
/* double dmin = 1e64;
 for (i = 0;i < N;i += 1)
  {
   for (long j = 0;j < N;j += 1)
    {
     if (i == j)
       {
        continue;
       }
     dmin = mind(dmin,Dist(i,j));
    }
  }
 fout << setprecision(15) << dmin;*/

 qsort(Puncte,N,sizeof(TPoint),CompareY);

 fout << setprecision(15) << DMX(0,N - 1);

 fin.close();
 fout.close();
 return 0;
}