Cod sursa(job #721269)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 23 martie 2012 15:23:05
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
// Implementare folosind un algoritm de baleiere
// 100 de puncte

#include<fstream>
#include<list>
#include<cmath>
#include<algorithm>
using namespace std;
int n;
typedef long long LL;
typedef pair<LL,LL> Punct;
Punct v[100100];
list <Punct> sweepline;
LL sol=1000000000000000001LL;

inline void Citire()
{
	int i;
	Punct A;
	ifstream fin("cmap.in");
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>A.first>>A.second;
		v[i]=A;
	}
	fin.close();
}

inline LL Dist(Punct A,Punct B)
{
	return (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);
}

void Rezolvare()
{
	int i;
	Punct curent,urmator;
	list <Punct>::iterator it;
	LL dist;
	sort(v+1,v+n+1);
	for(i=1;i<=n;i++)
	{
		curent=v[i];
		for(it=sweepline.begin();it!=sweepline.end();it++)
		{
			urmator=*it;
			dist=Dist(curent,urmator);
			if(curent.first-urmator.first>=sol)
			{
				sweepline.erase(it);
			}
			else
			{
				sol=min(sol,dist);
			}
		}
		sweepline.push_back(curent);
	}
}

inline void Afisare()
{
	freopen("cmap.out","w",stdout);
	printf("%.6lf\n",sqrt((double)sol));
}

int main()
{
	Citire();
	Rezolvare();
	Afisare();
	return 0;
}