Cod sursa(job #1082352)

Utilizator danny794Dan Danaila danny794 Data 14 ianuarie 2014 15:53:55
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.73 kb
#include <cstdio>
#include <algorithm>
#include <cmath>

#define minim(a, b) a > b ? b : a

using namespace std;

const float inf = 1 << 30;
const int NMAX = 100005;
int N;
pair<int, int> points[NMAX];
pair<int, int> 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("%i %i", &points[i].first, &points[i].second);
	sort(points, points + N);
}

inline float dist(int ax, int ay, int bx, int by) {
	return sqrt((ax - bx) * (ax - bx) * 1.0 + (ay - by) * (ay - by) * 1.0);
}

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

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

		for( int i = e; i <= x; i++ ) {
			for( int j = x + 1; j < e; j++ ) {
				if( points[i].second - pointY[j].first < min ) {
					float dm = dist(points[i].first, points[i].second, pointY[j].second, pointY[j].first);
					if( dm < min )
						min = dm;
				} else if ( points[i].second - pointY[j].first > min )
					break;
			}
		}
		return min;
	}
}

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