Cod sursa(job #673663)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 4 februarie 2012 19:24:22
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
#define NMAx 100100
#define ff first
#define ss second
#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) {
	
	double best;
	if(right-left<=2) {
		best=dist(V[left],V[right]);
		if(right-left==2) {
			best=min(best,dist(V[left],V[left+1]));
			best=min(best,dist(V[left+1],V[right]));
			}
		sort(Y+left,Y+right);
		return best;
		}

	int i,j,mid=(left+right)>>1;
	
	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;
}