Cod sursa(job #2466878)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 3 octombrie 2019 09:49:13
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.35 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <algorithm>

using namespace std;

ifstream fin ("cmap.in");
ofstream fout ("cmap.out");

const int MAXN = 1e5 + 5;
struct Point{
	
	int x,y;
	bool operator < ( const Point&  ob) const {
		return x < ob.x;
	};
};
Point p[MAXN],v[MAXN];

int n;
double dist( Point x,Point y) {
	
	return sqrt((x.x-y.x) * (x.x-y.x) + (x.y-y.y) * (x.y-y.y)); 
}

double solve(int st, int dr) {
	
	double ans = 10000000000;
	if ( dr - st <= 3) {
		
		for ( int i = st; i <= dr; ++i)
			for ( int j  = i + 1; j <= dr; ++j)
				ans = min(ans,dist(p[i],p[j]));
	return ans;
	}
	int mj;
	mj = ( st + dr) >>1;
	int xmij = p[mj].x;
	ans = min(solve(st,mj),solve(mj+1,dr));
	int i = st, j = mj +1,ind = 0;
	while ( i <= mj and j <= dr) {
		
		if ( p[i].y < p[j].y)
			v[++ind] = p[i++];
		else
			v[++ind] = p[j++];
	}
	for ( ; i <= mj ; ++i) v[++ind] = p[i];
	for ( ; j <= dr ; ++j) v[++ind] = p[j];
	for ( int i = st; i <= dr; ++i)
		p[i] = v[i];
	ind = 0;
	for ( int i = st; i <= dr; ++i)
		if ( fabs(p[i].x - xmij) < 	ans)
				v[++ind] = p[i];
	for ( int i = 1; i <= ind; ++i)
		for( int j = i + 1; j <= min(i + 7,ind); ++j)
			ans = min(ans,dist(v[i],v[j]));
	return ans;
}


int main() {
		
		fin >> n;
		for ( int i = 1; i <= n; ++i)
			fin >> p[i].x >> p[i].y;
	sort(p+1,p+1+n);
	fout << setprecision(8) << fixed;
	fout << solve(1,n);
}