Cod sursa(job #2049097)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 26 octombrie 2017 20:49:27
Problema Cele mai apropiate puncte din plan Scor 65
Compilator cpp Status done
Runda Arhiva educationala Marime 2.25 kb
#include <iostream>
#include <cstdlib>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <iomanip>

#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;
const long double INF = 4e18;

int n;
koordS p[NLIM];
koordS y[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 = INF;
    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 )
{
	//*/
	if( r - l <= 9 )
	{
		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:
	int ysize = 0;
    for( int i = m; i < r && abs( p[i].x - p[m].x ) <= s; ++i )
        if( abs( p[i].x - p[m].x ) < s )
            y[ysize++] = p[i];
	for( int i = m - 1; i >= l && abs( p[i].y - p[m].x ) <= s; --i )
        if( abs( p[i].x - p[m].x ) < s )
            y[ysize++] = p[i];

    sort( y, y + ysize, compary );

	//cout << ysize << "\n";

    ld hres = INF;
    for( int i = 0; i < ysize; ++i )//abs( p[j].y - p[i].y ) <= s //j - i < 8
        for( int j = i + 1; abs( p[j].y - p[i].y ) <= s && j < ysize; ++j )
        {
            ld ds = dist( p[i], p[j] );
            if( ds < hres )
                hres = ds;
        }
  
    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 << fixed << setprecision(6) << solve( 0, n )  << "\n";

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

    return 0;
}