Cod sursa(job #630456)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 5 noiembrie 2011 16:29:19
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream>
#include<algorithm>
#include<vector>
#include<iomanip>
#define sqr(a) (a)*(a)
#define dist(a,b) sqr(a.first-b.first)+sqr(a.second-b.second)
#define inf 2100000000
using namespace std;
vector<pair<int,int> > v,y,w(100100);
int n;
long long dei(int s,int d) {
	if(d-s<1)
		return inf;
	else if(d-s==1) {
		if(y[s].first<y[d].first)
			swap(y[s],y[d]);
		return dist(v[s],v[d]);
		}
	int mij=(s+d)/2,i,nr=0,j;
	long long best=min(dei(s,mij),dei(mij+1,d));
	merge(y.begin()+s,y.begin()+mij,y.begin()+mij+1,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)
			v[nr++]=y[i];
	for(i=0;i<nr-1;i++)
		for(j=i+1;j<i+8&&j<nr;j++)
			best=min(best,1LL*dist(v[i],v[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;
		y[i]=make_pair(v[i].second,v[i].first);
	}
	in.close();
}
int main() {
	int d;
	citire();
	sort(v.begin(),v.end());
	d=dei(0,n-1);
	ofstream out("cmap.out");
	out<<fixed<<setprecision(6)<<sqrt(d)<<'\n';
	out.close();
	return 0;
}