Cod sursa(job #777549)

Utilizator savimSerban Andrei Stan savim Data 12 august 2012 17:40:16
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>

using namespace std;

const int MAX_N = 100010;

const double inf = 2e+9;

int n, m;

struct element {
	int x, y;
} A[MAX_N], aux[MAX_N];

inline int cmp(const element &A, const element &B) {
	if (A.x == B.x)
		return A.y < B.y;
	return A.x < B.x;
}

inline int cmp_y(const element &A, const element &B) {
	if (A.y == B.y)
		return A.x < B.x;
	return A.y < B.y;
}

inline double sqr(double x) {
	return x * x;
}

inline double dist(const element &A, const element &B) {
	return sqrt(sqr(A.x - B.x) + sqr(A.y - B.y));
}

double solve(int st, int dr) {
	if (st == dr)
		return inf;
	
	if (st + 1 == dr)
		return dist(A[st], A[dr]);
	
	int mid = (st + dr) / 2;
	
	double d1 = solve(st, mid);	
	double d2 = solve(mid + 1, dr);
	
	double ans = min(d1, d2);
	
	m = 0;
	for (int i = st; i <= dr; i++)
		if ((A[i].x <= A[mid].x && A[i].x + ans >= A[mid].x) ||
			(A[i].x >= A[mid].x && A[i].x - ans <= A[mid].x))
				aux[++m] = A[i];
	sort(aux + 1, aux + m + 1, cmp_y);
		
	int last = 1;
	for (int i = 1; i <= m; i++) {
		while (aux[last].y + ans <= aux[i].y)
			last++;
		
		for (int j = last; j < i; j++)
			ans = min(ans, dist(aux[j], aux[i]));
	}
	
	return ans;
}

int main() {

	freopen("cmap.in", "r", stdin);
	freopen("cmap.out", "w", stdout);
	
	scanf("%d", &n);
	
	for (int i = 1; i <= n; i++)
		scanf("%d %d", &A[i].x, &A[i].y);
	
	sort(A + 1, A + n + 1, cmp);
	
	printf("%lf\n", solve(1, n));
	
	return 0;
}