Cod sursa(job #1983957)

Utilizator AeroHHorea Stefan AeroH Data 22 mai 2017 23:16:24
Problema Cele mai apropiate puncte din plan Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.84 kb
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<limits.h>
#include<float.h>
#define Nmax 100010
typedef struct { int x, y;}punct;
punct v[Nmax],w[Nmax];
int n;

int cmpfunc (const void * a, const void * b)
{
   return ( *(int*)a - *(int*)b );
}

double dist ( punct a, punct b)
{
    double difx=a.x-b.x;
    double dify=a.y-b.y;

    return sqrt ( difx*difx + dify*dify ) ;
}


double divide ( int st, int dr)
{
    if ( dr-st < 3 )
    {
        double D, Dmin=DBL_MAX;
        int i, j;

        for(i=st;i<dr;i++)
            for(j=i+1;j<=dr;j++)
            {
                D=dist(v[i],v[j]);
                if(D<Dmin)
                    Dmin=D;
            }
        return Dmin;
    }


    int m=(st+dr)/2;
    int d=v[m].x;

    double S1 = divide ( st, m ) ;
    double S2 = divide ( m+1, dr ) ;

    double S = S1;
    if(S2<S1) S=S2;

    int i,j=m+1,k=0;

    for(i=st;i<=m;i++)
        if( abs(v[i].x-d) <= S ) break;

    while( i <= m && j <= dr && abs(v[j].x-d) <= S )
        if( v[i].y < v[j].x ) w[++k]=v[i++];
        else                  w[++k]=v[j++];

    while ( i <= m ) w[++k]=v[i++];
    while ( j <= dr && abs(v[j].x-d) <= S ) w[++k]=v[j++];

    double D, Dmin=DBL_MAX;

    for(i=1;i<k;i++)
        for(j=i+1; j<=(i+7) && j<=k; j++)
        {
            D=dist(w[i],w[j]);
            if(D<Dmin) Dmin=D;
        }
    if(Dmin>S) Dmin=S;

    return Dmin;
}

int main()
{FILE *f,*g;
 int n;
 double min;
    f=fopen("cmap.in","r");
    g=fopen("cmap.out","w");
    fscanf(f,"%d",&n);
    int i;
    for(i=1;i<=n;i++)
        fscanf(f,"%d%d",&v[i].x,&v[i].y);

   qsort(v+1,n,8,cmpfunc);

   min=divide(0,n-1);
    fprintf(g,"%lf\n",min);
//  printf("%lf\n(%d %d) (%d %d)",dist(v[ci],v[cj]),v[ci].x,v[ci].y,v[cj].x,v[cj].y);
    return 0;
}