Cod sursa(job #2466913)

Utilizator Dobricean_IoanDobricean Ionut Dobricean_Ioan Data 3 octombrie 2019 11:12:40
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <algorithm>

using namespace std;

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

const int MAXN = 1e5 + 5;

#define x first
#define y second
using Point = pair < int ,int > ;
pair < int ,int > p[MAXN],v[MAXN];

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

bool cmp(Point x, Point y) {
	
	return (x.y < y.y);
}

double solve(int st, int dr) {
	
	double ans = INFINITY;
	if ( dr - st + 1 <= 3) {
		//sort(p+st+1,p+dr+1,cmp);
		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) / 2	;
	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-st+1];
	ind = 0;
	for (  i = st; i <= dr; ++i)
		if ( fabs(p[i].x - xmij) <= ans)
				v[++ind] = p[i];
	for (  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);
}