Cod sursa(job #756512)

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

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

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

long N;

TPoint Puncte[100005];
TPoint Temp[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;
}

void mergeX(long left,long mid,long right)
{
 long d1 = left;
 long d2 = mid + 1;
 long p = left;
 while ((d1 <= mid) && (d2 <= right))
  {
   if (Puncte[d1].X < Puncte[d2].X)
     {
      Temp[p] = Puncte[d1];
      d1 += 1;
     }
    else
     {
      Temp[p] = Puncte[d2];
      d2 += 1;
     }
   p += 1;
  }
 while (d1 <= mid)
  {
   Temp[p] = Puncte[d1];
   d1 += 1;
   p += 1;
  }
 while (d2 <= right)
  {
   Temp[p] = Puncte[d2];
   d2 += 1;
   p += 1;
  }
 memmove(Puncte + left,Temp + left,sizeof(TPoint) * (right - left + 1));
}

double DMX(long left,long right)
{
 if ((right - left) <= 3)
   {
    qsort(Puncte + left,right - left + 1,sizeof(TPoint),CompareX);
    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;
  }

 mergeX(left,mid,right);

 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;
}