Cod sursa(job #631256)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 7 noiembrie 2011 16:48:24
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include<fstream>
#include<algorithm>
#include<iomanip>
#include<cmath>
using namespace std;
pair<double,double > v[100100],y[100100],w[100100];
int n,i,j,nr;
double inf=2<<29,best,best2;
inline double dist2(pair<double,double> a,pair<double,double> b) {
	return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));
}
inline double dei(int s,int d) {
	if(s==d)
		return inf;
	else if(d-s==1) {
		if(y[s].first<y[d].first)
			swap(y[s],y[d]);
		return dist2(v[s],v[d]);
		}
	int mij=(s+d)/2;
	best=min(dei(s,mij),dei(mij+1,d));
	
	merge(y+s,y+mij,y+mij,y+d,w);
	copy(w,w+(d-s),y+s);
	
	for(i=s,nr=0,best2=best;i<=d;i++)
		if(abs(y[i].second-v[mij].first)<best2)
			w[nr++]=y[i];
			//best2=min(best2,abs(y[i].second-v[mij].first));
		
	for(i=0;i<nr-1;i++)
		for(j=i+1;j<i+8&&j<nr;j++)
			best=min(best,dist2(w[i],w[j]));
	
	return best;
}
void citire() {
	ifstream in("cmap.in");
	in>>n;
	for(i=0;i<n;i++)
		in>>v[i].first>>v[i].second;
	sort(v,v+n);
	for(i=0;i<n;i++)
		y[i]=make_pair(v[i].second,v[i].first);
	in.close();
}
int main() {
	citire();
	ofstream out("cmap.out");
	out<<fixed<<setprecision(6)<<dei(0,n-1)<<'\n';
	out.close();
	return 0;
}