Cod sursa(job #631250)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 7 noiembrie 2011 16:32:49
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<cmath>
#define sqr(a) (a)*(a)
#define dist(a,b) sqrtl(sqr(a.first-b.first)+sqr(a.second-b.second))
using namespace std;
vector<pair<double,double > > v,y,w(100100);
int n;
double inf=2<<29,best;
inline double dist2(pair<double,double> a,pair<double,double> b) {
	return sqrtl((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,i,nr=0,j;
	/*double */best=min(dei(s,mij),dei(mij+1,d));
	
	merge(y.begin()+s,y.begin()+mij,y.begin()+mij,y.begin()+d,w.begin());
	copy(w.begin(),w.begin()+d-s,y.begin()+s);
	
	for(i=s;i<=d;i++)
		if(abs(y[i].second-v[mij].first)<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,(double)dist2(w[i],w[j]));
	
	return best;
}
void citire() {
	int i;
	ifstream in("cmap.in");
	in>>n;
	v.resize(n);
	y.resize(n);
	for(i=0;i<n;i++)
		in>>v[i].first>>v[i].second;
	sort(v.begin(),v.end());
	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;
}