Cod sursa(job #1157300)

Utilizator SebiSebiPirtoaca George Sebastian SebiSebi Data 28 martie 2014 13:33:33
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include<iostream>
#include<fstream>
#include<vector>
#include<algorithm>
#include<math.h>
#include<iomanip>
using namespace std;

#define NMAX 100001
#define INF 1LL<<40
#define x first
#define y second

vector < pair < int , int > > v,aux1,aux2;

inline double dist(pair < int , int > a, pair < int , int > b)
{
	return sqrtl(0LL+1LL*(a.x-b.x)*(a.x-b.x)+1LL*(a.y-b.y)*(a.y-b.y));
}

double solve(int a, int b)
{
	if(a+1==b)
		return dist(v[a],v[b]);
	if(a+2==b) 
		return min(dist(v[a+1],v[a+2]),min(dist(v[a],v[a+1]),dist(v[a],v[a+2])));
	int mij;
	mij=(a+b)/2;
	double d1 = solve(a,mij);
	double d2 = solve(mij,b);
	double sol;
	int i,j,k,n1,n2;
	d1 = min(d1,d2);
	sol = INF;
	for(i=mij;i<=b && (double)(v[i].x-v[mij].x)<=d1;i++)
		aux2.push_back(make_pair(v[i].y,v[i].x));
	for(i=mij;i>=a && (double)(v[mij].x-v[i].x)<=d1;i--)
		aux1.push_back(make_pair(v[i].y,v[i].x));
	sort(aux1.begin(),aux1.end());
	sort(aux2.begin(),aux2.end());
	n1=aux1.size()-1;
	n2=aux2.size()-1;
	j=0;
	for(i=0;i<=n1;i++) {
		while(j<=n2 && (double)(aux2[j].x+d1)<aux1[i].x) 
			j++;
		for(k=j;k<=n2 && (k-j)<=7;k++)
			if(aux1[i].x!=aux2[k].x || aux1[i].y!=aux2[k].y)
				sol=min(sol,dist(aux1[i],aux2[k]));
	}
	aux1.clear();
	aux2.clear();
	return min(sol,d1);
}

int main ()
{
	int i,n;
	ifstream f("cmap.in");
	ofstream g("cmap.out");
	f>>n;
	v.resize(n+1);
	for(i=1;i<=n;i++)
		f>>v[i].x>>v[i].y;
	f.close();
	sort(v.begin()+1,v.end());
	g<<fixed;
	g<<setprecision(6)<<solve(1,n)<<'\n';
	g.close();
	return 0;
}