Cod sursa(job #2076673)

Utilizator ArctopusKacso Peter-Gabor Arctopus Data 26 noiembrie 2017 22:05:07
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.19 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>


#define ll long long 
#define ld long double
const int NLIM = 1e5 + 10;
const ld INF = INT_MAX;

using namespace std;

struct pointS
{
	ld x, y;
};

int comparX( const void* a, const void* b )
{
	pointS p1 = *(pointS*)a;
	pointS p2 = *(pointS*)b;

	if( p1.x < p2.x ) return -1;
	if( p1.x > p2.x ) return 1;

	if( p1.y < p2.y ) return -1;
	if( p1.y > p2.y ) return 1;
	return 0;
}
int comparY( const void* a, const void* b )
{
	pointS p1 = *(pointS*)a;
	pointS p2 = *(pointS*)b;

	if( p1.y < p2.y ) return -1;
	if( p1.y > p2.y ) return 1;

	if( p1.x < p2.x ) return -1;
	if( p1.x > p2.x ) return 1;
	return 0;
}


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

int n;
pointS points[NLIM];
pointS strip[NLIM];


ld solve( int l, int r )
{
	
	if( l + 3 >= r )
	{
		// small bruteforce
		ld res = INF;
		for( int i = l; i < r; ++i )
			for( int j = i + 1; j < r; ++j )
			{
				ld d = dist(points[i], points[j]);
				if( d < res )
					res = d;
			}
		return res;
	}
	// middle
	int m = ( l + r ) / 2;
	// minimum of left and right thing
	ld res = min( solve( l, m ), solve( m + 1, r ) );
	

	// calc middle
	int stripSize = 0;
	for( int i = l; i < r; ++i )
		if( abs( points[i].x - points[m].x ) < res )
			strip[stripSize] = points[i], stripSize++; 

	// sort by Y
	qsort( strip, stripSize, sizeof( pointS ), comparY );
	for( int i = 0; i < stripSize; ++i )
		for( int j = i + 1; j < stripSize && ( strip[j].y - strip[i].y ) < res; ++j )
		{
			ld d = dist( strip[i], strip[j] );
			if( d < res )
				res = d;
		}

	return res;
}

ifstream fcin("cmap.in");
ofstream fcout("cmap.out");
int main()
{
	fcin >> n;

	for( int i = 0; i < n; ++i )
		fcin >> points[i].x >> points[i].y;

	qsort( points, n, sizeof( pointS ), comparX );

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

	fcout << fixed << setprecision(6)  << solve( 0, n ) << "\n";
	

	
}