Cod sursa(job #2298919)

Utilizator danielsociuSociu Daniel danielsociu Data 8 decembrie 2018 17:08:18
Problema Cele mai apropiate puncte din plan Scor 5
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 int inf=0x3f3f3f3f;
#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(st>=dr-1)
		return inf;
	else if(st-dr==2){
		if(y[st]>y[st+1])
			swap(y[st],y[st+1]);
		return calc(x[st],x[st+1]);
	}
	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;
		for(i=1;i<=n;i++){
			cin>>a>>b;
			x.push_back(make_pair(a,b));
		}
		sort(x.begin(),x.end());
		y.resize(n);
		for(i=0;i<n;i++)
			y[i]=make_pair(x[i].second,x[i].first);

		cout<<fixed<<setprecision(6)<<sqrt(solve(0,x.size()-1));
		return 0;
}