Cod sursa(job #1371585)

Utilizator rughibemBelcineanu Alexandru Ioan rughibem Data 3 martie 2015 22:30:28
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.34 kb
#include<stdio.h>
#include<math.h>
#include<algorithm>
#define MAXN 100005
#define INF 1LL<<61
FILE *f=fopen("cmap.in","r"), *g=fopen("cmap.out","w");

using namespace std;

struct Puncte{
    long long int x, y;
}   X[MAXN], Y[MAXN], t[MAXN], sir[MAXN];

    // X = sortat dupa X
    // Y = sortat dupa Y (se va afla prin interclasare)
    // t = ajutor pentru interclasare
    // sir = doar cele care sunt la distanta <= solutia momentana

long long int N;

bool cmp( Puncte A, Puncte B ){
    if( A.x < B.x || ( A.x == B.x && A.y < B.y ) ) return 1;
    return 0;
}

long long int Distanta( Puncte A, Puncte B ){
    return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
}

void Citire(){
long long int i;

    fscanf(f,"%lld\n",&N);
    for(i=1;i<=N;i++)
        fscanf(f,"%lld %lld\n",&X[i].x,&X[i].y);
        sort(X+1,X+N+1,cmp);
}

void Interclaseaza( long long int k1, long long int mij, long long int k2 ){
long long int i, j, k;

    i = k1; k = k1-1; j = mij+1;

    while( i<=mij && j<=k2 )
        if( Y[i].y < Y[j].y ) t[++k] = Y[i++];
        else                  t[++k] = Y[j++];

    while( i<=mij ) t[++k] = Y[i++];
    while( j<=k2  ) t[++k] = Y[j++];

    for(i=k1;i<=k2;i++) Y[i] = t[i];

}

long long int DMIN( long long int k1, long long int k2 ){
long long int dmin, i, j, mij, Lsir;

    if( k2-k1+1 <= 3 ){ // Mai putin de 3 puncte

        for(i=k1;i<=k2;i++) Y[i] = X[i];

        for(i=k1;i<k2;i++)              // Sortare dupa Y
            for(j=i+1;j<=k2;j++)
                if( Y[i].y > Y[j].y ) swap( Y[i], Y[j] );

        if( k1 == k2 ) return INF;

        dmin = Distanta( X[k1], X[k1+1] );
        for(i=k1;i<k2;i++)              // Distantele dintre cele 2 sau 3 puncte
            for(j=i+1;j<=k2;j++)
                dmin = min( Distanta( X[i], X[j] ), dmin );

        return dmin;
    }

    mij = (k1+k2)/2;
    dmin = min( DMIN(k1,mij), DMIN(mij+1,k2) );

    Interclaseaza( k1, mij, k2 );

    Lsir = 0;
    for(i=k1;i<=k2;i++)
        if( abs( Y[i].x - Y[mij].x ) <= dmin ) sir[++Lsir] = Y[i];



    for(i=1;i<=Lsir;i++)
        for(j=1; j<=7 && i+j <= Lsir; j++)
            dmin = min( Distanta(sir[i],sir[i+j]) , dmin );

    return dmin;

}

int main(){

    Citire();
    fprintf(g,"%.6lf\n", sqrt( DMIN(1,N) ) );

return 0;
}