Cod sursa(job #933186)

Utilizator raulstoinStoin Raul raulstoin Data 29 martie 2013 17:59:12
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.35 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<cmath>
#define LL long long
#define left Y.begin()+s
#define middle Y.begin()+m
#define right Y.begin()+d
#define PAIR pair<LL,LL> 
using namespace std;
vector <PAIR> X,Y,V(100005);
int n;
LL oo=(1LL<<62);
void read()
{
	ifstream fin("cmap.in");
	LL x,y;
	fin>>n;
	for(LL i=0;i<n;i++)
	{
		fin>>x>>y;
		X.push_back(make_pair(x,y));
	}
	sort(X.begin(),X.end());
	for(int i=0;i<n;i++)
		Y.push_back(make_pair(X[i].second,X[i].first));
	fin.close();

}
inline LL dist(PAIR A,PAIR B)
{
	return (B.first-A.first)*(B.first-A.first)+(B.second-A.second)*(B.second-A.second);
}
inline LL solve(LL s,LL d,vector<PAIR> &X,vector<PAIR> &Y)
{
	if(s>=d-1)
		return oo;
	if(s+2==d)
	{
		if(Y[s]>Y[s+1])
			swap(Y[s],Y[s+1]);
		return dist(Y[s],Y[s+1]);
	}
	int m=(s+d)/2;
	LL best=min(solve(s,m,X,Y),solve(m,d,X,Y));
	merge(left,middle,middle,right,V.begin());
	copy(V.begin(),V.begin()+(d-s),left);
	size_t SIZE=0;
	for(int i=s;i<d;i++)
		if(abs(Y[i].second-X[m].first)<=best)
			V[SIZE++]=Y[i];
	for(size_t i=0;i<SIZE-1;i++)
		for(size_t j=i+1;j<SIZE && j-i<8;j++)
			best=min(best,dist(V[i],V[j]));
	return best;
}
int main()
{
	read();
	ofstream fout("cmap.out");
	fout.precision(7);
	fout<<fixed<<sqrt(double(solve(0,X.size(),X,Y)));
	fout.close();
	return 0;
}