Cod sursa(job #1435460)

Utilizator paul_danutDandelion paul_danut Data 13 mai 2015 12:17:05
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.52 kb
#include <fstream>
#include <algorithm>
#include <math.h>
#include <iomanip>
using namespace std;

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


struct point{long int x,y;}a[100001],aux[100001];
int n;
struct func{
    bool operator()(point x,point y) const
      {  return x.x < y.x;   }
};

double ddistance(point a,point b)
{
    return (double) sqrt( (double) ((a.x-b.x) * (a.x-b.x) + (a.y-b.y) * (a.y-b.y) ));
}
void merge(int s,int d,int m)
{
    int i=s, j=m+1,k=0;
    while(i<=m && j<=d)
          if(a[i].y >= a[j].y)
              {aux[k++]=a[j];
              j++;}
          else
              {aux[k++]=a[i];
              i++;}
    if(i<=m)
        for(j=i;j<=m;j++)
             aux[k++]=a[j];
    else
        for(i=j;i<=d;i++)
             aux[k++]=a[i];
    for(int o=0;o<k;o++)
        a[s+o]=aux[o];
}
int abs(int x,int y)
{
    int val=x-y;
    if(val>=0)
        return val;
    else
        return -val;
}
double find2(int s,int d,int m,double dist)
{
    int nr=0,i,j;
    merge(s,d,m);
    for(i=s;i<=d;i++)
         if( abs(a[i].x, m) <= dist )
              {nr=0;
               for(j=i+1; j<=d && nr!=7; j++)
                    if(abs(a[j].x, m)<= dist  && abs(a[j].y, a[i].y) <= dist)
                           {nr++;
                           if(ddistance(a[i], a[j])<dist)
                                dist=ddistance(a[i], a[j]);}}
    return dist;
}
void order(int s,int d)
{
    if( d-s == 1 )
        {
        if( a[s].y > a[d].y )
            swap( a[s], a[d] );
        }
    else
        if( a[s].y > a[s+1].y )
            if( a[s+1].y > a[d].y )
                swap( a[s], a[d] );
            else
                swap( a[s], a[s+1] );
        else
            if(a[s].y > a[d].y)
                {swap( a[s], a[d] );
                swap( a[s+1], a[d] );}
            else
                if(a[s+1].y > a[d].y)
                    swap( a[s+1], a[d] );
}
double find(int s,int d)
{
    if( d-s <= 2 )    ///daca mai sunt 3 puncte
        {order(s,d);
        if( d-s == 1 )
             return ddistance( a[s], a[d] );
        else

             return min( min(ddistance(a[s], a[s+1]), ddistance(a[s+1], a[d])), ddistance(a[s],a[d]) );}
    else
        {
            int m=s+(d-s)/2;
            return find2(s, d, m, min(find(s, m), find(m+1, d)));
        }
}
int main()
{
    f>>n;
    for(int i=1;i<=n;i++)
        f>>a[i].x>>a[i].y;
    sort(a+1,a+n+1,func());
    g<<std::fixed<<setprecision(6)<<find(1,n);

}