Cod sursa(job #673658)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 4 februarie 2012 19:19:19
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#define NMAx 100100
#define ff first
#define ss second
#define oo (1<<30)
#define pp(a) (a)*(a)
#define dist(a,b) sqrt(pp(a.ff-b.ff)+pp(a.ss-b.ss))
using namespace std;
pair<double,double > V[NMAx],Y[NMAx],w[NMAx];
int n,nr;

double dei(int left,int right) {
	
	if(left==right)
		return oo;
	else if(right-left==1) {
			if(Y[left].ff>Y[right].ff)
				swap(Y[left],Y[right]);
			return dist(V[left],V[right]);
			}

	int i,j,mid=(left+right)>>1;
	double best;
	
	best=min(dei(left,mid),dei(mid,right));
	
	merge(Y+left,Y+mid,Y+mid,Y+right,w);
	copy(w,w+(right-left),Y+left);
	
	for(i=left,nr=0;i<=right;i++)
		if(abs(Y[i].ss-V[mid].ff)<=best)
			w[nr++]=Y[i];
		
	for(i=0;i<nr-1;i++)
		for(j=i+1;j<i+8&&j<nr;j++)
			best=min(best,dist(w[i],w[j]));
	
	return best;
}
void citire() {
	
	int i;
	ifstream in("cmap.in");
	
	in>>n;
	for(i=0;i<n;i++)
		in>>V[i].ff>>V[i].ss;
	
	sort(V,V+n);
	
	for(i=0;i<n;i++)
		Y[i]=make_pair(V[i].ss,V[i].ff);
	
	in.close();
}
int main() {
	
	citire();

	ofstream out("cmap.out");
	out<<fixed<<setprecision(6)<<dei(0,n-1)<<'\n';
	out.close();

	return 0;
}