Cod sursa(job #436198)

Utilizator s_holmesSherlock Holmes s_holmes Data 8 aprilie 2010 12:14:31
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define NMAX 100010
#define ll long long
int N;
pair<ll, ll> X[NMAX];
pair<ll, ll> Y[NMAX];
pair<ll, ll> V[NMAX];

void citire()
{
	scanf("%d",&N);
	for(int i = 1 ; i <= N ; i ++)
		scanf("%lld%lld", &X[i].first, &X[i].second);
	sort(X + 1, X + N + 1);
	for(int i = 1 ; i <= N ; i++)
		Y[i] = make_pair(X[i].second, X[i].first);
}

ll modul(ll x)
{
	if(x < 0)
		return -x;
	return x;	
}

ll dist(const pair<ll, ll> &a, const pair<ll, ll> &b)
{
	return modul((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

ll rezolva(int st, int dr)
{
	if(st >= dr)
		return 1LL << 62;
	if(st + 1 == dr)
	{
		if(Y[st] > Y[dr])
			swap(Y[st], Y[dr]);
		return dist(X[dr], X[st]);
	}
	int m = (st + dr)>>1;
	ll rez = min(rezolva(st, m), rezolva(m + 1, dr));
	merge(Y + st, Y + m + 1, Y + m + 1, Y + dr + 1, V);
	copy(V, V + (dr - st) + 1, Y + st);
	
	int lim = 0;
	for(int i = st ; i <= dr ; i++)
		if(modul(Y[i].second - X[i].first) <= rez)
			V[++lim] = Y[i];
	
	for(int i = st; i < dr ; i ++)
		for(int j = i + 1 ; j <= min(i + 7, lim) ; j++)
			rez = min(rez, dist(V[j], V[i]));
		
	return rez;
}

int main()
{
	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);
	citire();
	ll rez = rezolva(1, N);
	printf("%lf",sqrt((double)rez));
	
	return 0;
}