Cod sursa(job #1082607)

Utilizator danny794Dan Danaila danny794 Data 14 ianuarie 2014 20:18:00
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

typedef long long ll;
#define minim(a, b) a > b ? b : a

using namespace std;

const double inf = 1 << 30;
const int NMAX = 100005;
int N;
pair<ll, ll> points[NMAX];
pair<ll, ll> pointY[NMAX];

void read() {
	freopen( "cmap.in", "r", stdin );
	freopen( "cmap.out", "w", stdout );
	scanf("%i", &N);
	for( int i = 0; i < N; i++ )
		scanf("%lld %lld", &points[i].first, &points[i].second);
	sort(points, points + N);
}

inline double dist(pair<ll, ll> a, pair<ll, ll> b) {
	return sqrt((a.first - b.first) * (a.first - b.first) * 1.0 + (a.second - b.second) * (a.second - b.second) * 1.0);
}

double solve(int a, int b) {
	if ( b - a < 3) {
		double min = inf;
		for( int i = a; i < b; i++ )
			for( int j = i + 1; j <= b; j++) {
				double d = dist(points[i], points[j]);
				if( d < min)
					min = d;
			}
		return min;
	} else {
		ll x = (a + b) >> 1;
		double p1 = solve(a, x);
		double p2 = solve(x + 1, b);
		double min = minim(p1, p2);
		double d = ( points[x + 1].first + points[x].first ) / 2.0;
		int s = x, e = x + 1;
		while( s >= a && d - points[s].first <= min )
			s--;
		s += 1;
		while( e <= b && points[e].first - d <= min)
			e++;

		for( int k = s; k < e; k++ )
			pointY[k] = make_pair(points[k].second, points[k].first);
		sort(pointY + s, pointY + e);

		for( int i = s; i < e - 1; i++ )
			for( int j = i + 1; j < e && j - i < 5; j++ ) {
				double d = dist(pointY[i], pointY[j]);
				min = minim(min, d);
			}
		return min;
	}
}

int main() {
	read();
	printf("%.6lf", solve(0, N - 1));
	return 0;
}