Cod sursa(job #1257610)

Utilizator jordasIordache Andrei Alexandru jordas Data 7 noiembrie 2014 22:49:08
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.27 kb
#include <fstream>
#include <cstdlib>
#include <math.h>

using namespace std;

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

 struct coordinates
   {float x;
    float y;
   };

 int i,n;
 coordinates points[100010];

 void read()
   {x>>n;
       n=0;
    while(x>>points[++n].x && x>>points[n].y);
    n=n-1;
    /*Test if we read correctly
    for(i=1;i<=n;i++)
      y<<points[i].x<<" "<<points[i].y<<"\n";
    */
   }

 float quicksort_x (coordinates v[], int l, int r)
   {if(l>=r)
      return 1;

    int poz,pivot,i,j;
    coordinates aux;

    poz=rand()%(r-l)+l+1;
    aux=v[l];
    v[l]=v[poz];
    v[poz]=aux;

    pivot=v[l].x;
    poz=l;
    i=l+1;
    for(j=l+1;j<=r;j++)
      if(v[j].x<pivot)
        {aux=v[j];
         v[j]=v[i];
         v[i]=aux;
         i++;
         /*
         int k;
         y<<j<<" --> ";
         for(k=1;k<=n;k++)
           y<<v[k].x<<" ";
         y<<'\n';
         */
        }
    aux=v[poz];
    v[poz]=v[i-1];
    v[i-1]=aux;

    quicksort_x(v,l,i-2);
    quicksort_x(v,i,r);
   }

 float distance(float ax, float ay, float bx, float by)
   {float d1,d2,d;
    d1=ax-bx;
    d2=ay-by;
    d=sqrt(d1*d1+d2*d2);
    return d;
   }

 float closest_pair(coordinates v[],int n)
   {if(n<=1)
      return 999999999;
    if(n==2)
      return distance(v[1].x, v[1].y, v[2].x, v[2].y);

    int n1=0,n2=0;
    float dist,DLmin,DRmin;
    coordinates v1[n/2+2],v2[n/2+2];

    for(i=1;i<=n;i++)
      if(i<=n/2)
        v1[++n1]=v[i];
      else
        v2[++n2]=v[i];

    DLmin=closest_pair(v1,n1);
    DRmin=closest_pair(v2,n2);
    dist=min(DLmin,DRmin);

    //trial #2
    float l1,l2,d,minn;
    int c1,c2;
    l1=v1[n1].x-dist;
    l2=v2[1].x+dist;
    minn=dist;
    for(c1=1;c1<=n1;c1++)
      if(v1[c1].x>=l1)
        for(c2=1;c2<=n2;c2++)
          if(v2[c2].x<=l2)
            {d=distance(v1[c1].x, v1[c1].y, v2[c2].x, v2[c2].y);
             if(d<minn)
               minn=d;
            }
    //end trial #2
    return min(dist,minn);
   }

int main()
{read();
 quicksort_x(points,1,n);
 /*//Test if sort is working properly
 for(i=1;i<=n;i++)
   y<<points[i].x<<" "<<points[i].y<<"\n";
 */
 y<<closest_pair(points,n);
}
//1761.154735