Cod sursa(job #2048975)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 26 octombrie 2017 19:00:26
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.24 kb
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>

#define ll long long
#define ld long double


using namespace std;

struct koordS
{
    ll x, y;
};

bool myfunction (int i,int j) { return (i<j); }

bool compar( koordS k1, koordS k2 )
{
    return k1.x < k2.x;
}

bool compary( koordS k1, koordS k2 )
{
    return k1.y < k2.y;
}

const int NLIM = 1e5 + 10;

int n;
koordS p[NLIM];

ld dist( koordS p1, koordS p2 )
{
    return sqrt( (p1.x - p2.x)*(p1.x - p2.x) + ( p1.y - p2.y )*( p1.y - p2.y ) );
}

ld kevesPontCucc( int l, int r )
{
    ld res = 99999999;
    for( int i = l; i < r; ++i )
    {
        for( int j = i + 1; j <= r; ++j )
        {
            ld d = dist( p[i], p[j] );
            if( d < res )
                res = d;
        }
    }

    return res;
}

int gi = 0;
ld solve( int l, int r )
{
	cout << gi++ << "\n";
    if( l + 4 > r )
    {
        return kevesPontCucc( l, r );
    }


    int m = ( l + r ) / 2;

    ld lr = solve( l, m );
    ld rr = solve( m + 1, r );

    ld s = min( lr, rr );

    // combine:
    vector< koordS > y;
    for( int i = m; i < n && abs( p[i].x - p[m].x ) < s; ++i )
    {
        if( abs( p[i].x - p[m].x ) < s )
            y.push_back( p[i] );
    }

	for( int i = m - 1; i >= 0 && abs( p[i].x - p[m].x ) < s; --i )
    {
        if( abs( p[i].x - p[m].x ) < s )
            y.push_back( p[i] );
    }


    sort( y.begin(), y.end(), compary );

    ld hres = 99999999;
    for( int i = 0; i < y.size(); ++i )
    {
        for( int j = i + 1; abs( p[j].y - p[i].y ) < s; ++j )
        {
            ld ds = dist( p[j], p[i] );
            if( ds < hres )
                hres = ds;
        }
    }
   // cout << "  " << hres << "\n";


    return min( hres, s );
}


ifstream fcin("cmap.in");
ofstream fcout("cmap.out");
int main()
{
    fcin >> n;
    for( int i = 0; i < n; ++i )
    {
        fcin >> p[i].x >> p[i].y;
    }

    sort( p, p + n, compar );


    fcout << solve( 0, n - 1 );

    fcout << "\n";
    /*/
    for( int i = 0; i < n; ++i )
    {
        cout << p[i].x << " " << p[i].y << "\n";
    }//*/

    return 0;
}