Cod sursa(job #2067639)

Utilizator andronierRobu Stefan andronier Data 16 noiembrie 2017 17:54:52
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.89 kb
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>

using namespace std;

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

#define Nmax 100010
#define Inf 1<<30

struct punct
{
    int x, y;
}v[Nmax],w[Nmax];

int n;

int cmp (punct a, punct b)
{
    if(a.x == b.x)
        return a.y < b.y;
    return a.x < b.x;
}

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=Inf;
        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].y )
            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=Inf;

    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()
{
    int n;
    f >> n;

    for ( int i = 1; i <= n ;i++)
        f >> v[i].x >> v[i].y;

    sort(v+1,v+n+1,cmp);

    g << fixed << setprecision(6) << divide(1,n);

    return 0;
}