Cod sursa(job #2299175)

Utilizator danielsociuSociu Daniel danielsociu Data 9 decembrie 2018 00:03:53
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 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;

int n;
vector<pair<ll,ll> > x;
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=min(ans,calc(x[i],x[j]));
		return ans;
	}
	int mij=(st+dr)/2;
	ll best=min(solve(st,mij),solve(mij+1,dr));

	vector<pair<int,int> > aux;
	for(int i=st;i<=dr;++i)
		if(best>=abs(x[i].first-x[mij].first))
			aux.push_back(x[i]);
	int counter=aux.size();
	sort(aux.begin(),aux.end(), [](auto &left, auto &right) {
    return left.second < right.second;
});
	for(int i=0;i<counter-1;++i)
		for(int j=i+1;j<counter&&(j-i<8);++j)
			best=min(calc(aux[i],aux[j]),best);
	return best;
}

int main()
{
		int i;
		cin>>n;
		x.resize(n+1);
		for(i=1;i<=n;i++)
			cin>>x[i].first>>x[i].second;
		sort(x.begin(),x.end());
		cout<<fixed<<setprecision(6)<<sqrt(solve(1,n));
		return 0;
}