Cod sursa(job #2298940)

Utilizator danielsociuSociu Daniel danielsociu Data 8 decembrie 2018 17:27:52
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
ifstream cin("cmap.in");
ofstream cout("cmap.out");
#define maxn 100005
#define ll long long
const ll inf=4e18;
#define minim(a,b) a<b?a:b

int n;
vector<pair<ll,ll> > x,y,Z(maxn);
ll calc(const pair<ll,ll> a,const pair<ll,ll> b){
	return ((a.first-b.first)*(a.first-b.first) + (a.second-b.second)*(a.second-b.second));
}

ll solve(int st,int dr)
{
	if(dr-st<=3){
		ll ans=inf;
		for (int i=st;i<dr;i++)
			for (int j=i+1;j<=dr;j++)
				ans=minim(ans,calc(x[i],x[j]));
		return ans;
	}
	int mij=(st+dr)/2;
	ll best=minim(solve(st,mij),solve(mij+1,dr));
	merge(y.begin()+st,y.begin()+mij,y.begin()+mij,y.begin()+dr,Z.begin());
	copy(Z.begin(),Z.begin()+(dr-st),y.begin()+st);

	int counter=0;
	for(int i=st;i<=dr;++i)
		if(best>=abs(y[i].second-x[mij].first))
			Z[counter++]=y[i];
	for(int i=0;i<counter-1;++i)
		for(int j=i+1;j<counter&&j-i<8;++j)
			best=minim(calc(Z[i],Z[j]),best);
	return best;
}

int main()
{
		int i,a,b;
		cin>>n;
		x.resize(n+1);
		for(i=1;i<=n;i++)
			cin>>x[i].first>>x[i].second;
		sort(x.begin(),x.end());
		y.resize(n+1);
		for(i=1;i<=n;i++)
			y[i]=make_pair(x[i].second,x[i].first);

		cout<<fixed<<setprecision(6)<<sqrt(solve(1,n));
		return 0;
}