Cod sursa(job #418824)

Utilizator laserbeamBalan Catalin laserbeam Data 16 martie 2010 15:17:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <cstdio>
#include <cmath>
#include <utility>
#include <vector>
#include <algorithm>
using namespace std;

#define NMAX 100005
#define FIN "cmap.in"
#define FOUT "cmap.out"

typedef long long i64;
typedef pair<i64, i64> pct;
pct X[NMAX], Y[NMAX], Aux[NMAX];
int N;
// X - punctele  sortate  dupa x -> first = x, second = y
// Y - punctele "sortate" dupa y -> first = y, second = x
// Y se sorteaza in timpul rezolvarii

const i64 INF = 4e18;

i64 dist(pct a, pct b)
{
	return (a.first - b.first) * (a.first - b.first) + \
		   (a.second - b.second) * (a.second - b.second);
}
i64 doSmartStuff(int st, int dr)
{
	if (st >= dr) return INF;
	if (dr - st == 1)
	{
		if (Y[st] > Y[dr]) swap(Y[st], Y[dr]);
		return dist(X[st], X[dr]);
	}
	int mij = (st+dr)/2;
	i64 rez = min( doSmartStuff(st, mij), doSmartStuff(mij+1, dr) );
	merge(Y+st, Y+mij+1, Y+mij+1, Y+dr+1, Aux);
	copy(Aux, Aux+dr-st+1, Y+st);
	
	int nr = 0;
	for (int i = st; i <= dr; ++i)
		if (abs(Y[i].second - X[mij].first) < rez) Aux[++nr] = Y[i];
	
	for (int i = 1; i < nr; ++i)
	{
		for (int j = i+1; j <= nr && j < i+8; ++j)
			rez = min(rez, dist(Aux[i],Aux[j]));
	}
	return rez;
	
}


int main()
{
	freopen(FIN,"r",stdin);
	freopen(FOUT,"w",stdout);
	
	scanf("%d ",&N);
	for (int i = 1; i <= N; ++i)
	{
		int alfa = 0;
		int beta = 0;
		scanf("%d %d ", &alfa, &beta);
		X[i] = make_pair((i64)alfa, (i64)beta);
	}

//	fprintf(stderr, "\n--------\n");
//	for (int i = 1; i <= N; ++i)
//		fprintf(stderr, "%lld %lld - %lld %lld\n", X[i].first, X[i].second, Y[i].first, Y[i].second);
//	fprintf(stderr, "\n--------\n");
	
	sort(X+1, X+N+1);
	for (int i = 1; i <= N; ++i)
		Y[i] = make_pair(X[i].second, X[i].first);
	
//	for (int i = 1; i <= N; ++i)
//		fprintf(stderr, "%lld %lld - %lld %lld\n", X[i].first, X[i].second, Y[i].first, Y[i].second);
	
	printf("%.6lf\n", sqrt(doSmartStuff(1, N)));
	
	
	return 0;
}