Cod sursa(job #1629573)

Utilizator IgorDodonIgor Dodon IgorDodon Data 4 martie 2016 16:30:24
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.54 kb
#include<stdio.h>
#include<limits.h>
#include<math.h>
#include<algorithm>
#define INF LONG_LONG_MAX
#define lli long long int
#define MAXM 100005
FILE *f=fopen("cmap.in","r"), *g=fopen("cmap.out","w");

using namespace std;

struct Punct{ lli x, y; };

int M, Ls;
Punct X[MAXM], Y[MAXM], newY[MAXM], s[MAXM];

    // X = sortat in functie de x
    // Y = pe parcurs sortat in functie de y

bool cmpX( Punct A, Punct B ){

    if( A.x < B.x || ( A.x == B.x && A.y < B.y ) )
        return 1;
        return 0;
}

bool cmpY( Punct A, Punct B ){

    if( A.y < B.y || ( A.y == B.y && A.x < B.x ) )
        return 1;
        return 0;

}

void Citire(){
int i;

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

    sort(X+1,X+M+1,cmpX);

    for(i=1;i<=M;i++)
        Y[i] = X[i];
}

lli Dist( Punct A, Punct B ){ return (A.x-B.x)*(A.x-B.x) + (A.y-B.y)*(A.y-B.y); }

void Interclasare( int K1, int mij, int K4, lli dminf ){
int i, K2, K3, LnewY = K1-1, LK12, LK34;

    K2 = mij;       // K1-K2 prima jumatate sortata corect      LK12 parcurgerea
    K3 = mij+1;     // K3-K4 a doua jumatate sortata corect     LK34 parcurgerea

    LK12 = K1;
    LK34 = K3;

    while( LK12 <= K2 && LK34 <= K4 ){

        if( cmpY( Y[LK12], Y[LK34] ) )
            newY[++LnewY] = Y[LK12++];
        else
            newY[++LnewY] = Y[LK34++];
    }
    while( LK12 <= K2 )
        newY[++LnewY] = Y[LK12++];
    while( LK34 <= K4 )
        newY[++LnewY] = Y[LK34++];

    for(i=K1;i<=K4;i++)
        Y[i] = newY[i];

    // s va contine doar elementele la distanta cel mult d de mij
    Ls = 0;
    for(i=K1;i<=K4;i++)
        if( abs( Y[i].x - X[mij].x ) <= dminf )
            s[++Ls] = Y[i];
}

lli DistMin( int K1, int K2 ){
int i, j, mij;
lli dmin = INF;

    if( K2-K1+1 <= 3 ){

        for(i=K1;i<K2;i++)
            for(j=i+1;j<=K2;j++)
                dmin = min( dmin, Dist( X[i], X[j] ) );

        // Sortare Y
        for(i=K1;i<K2;i++)
            for(j=i+1;j<=K2;j++)
                if( !cmpY( Y[i], Y[j] ) )
                     swap( Y[i], Y[j] );

        return dmin;
    }

    mij = ( K1 + K2 ) / 2;

    dmin = min( DistMin( K1, mij ), DistMin( mij+1, K2 ) );

    Interclasare( K1, mij, K2,  dmin );


    for(i=1;i<Ls;i++)
        for(j=i+1;j<=i+7 && j<=Ls;j++)
            dmin = min( dmin, Dist( s[i], s[j] ) );

    return dmin;
}

int main(){

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

return 0;
}