Cod sursa(job #406596)

Utilizator dornescuvladVlad Eugen Dornescu dornescuvlad Data 1 martie 2010 17:41:31
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include<iostream>
#include<fstream.h>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<math.h>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

struct point
{
	long long  x,y;
};

long long lin,col,n;
double rez1,rez2,rez3;
point punct;

vector<point> v;
vector<int>::iterator it;

long long i,min=2502500,rez;

double teta(point p1, point p2)
	{
		return sqrt((double)((long long)((long long)p1.x-p2.x)*(p1.x-p2.x)+(long long)((long long)p1.y-p2.y)*(p1.y-p2.y)));
	}



bool compare(point a, point b)
{
	return (b.x>a.x);
}


double Divide_and_Conquer(long long st, long long dr,long long n)
{   
	double minim=2481294;
	int i=0;
	int j=0;
	double dist;
	for(i=0;i<n;i++)
		for(j=i+1;j<n;j++)
			if(st<=v[i].x && v[i].x<=dr && st<=v[j].x && v[j].x<=dr)
			{
				dist=teta(v[i],v[j]);
				if(dist<minim)
					minim=dist;
			}
	return minim;
}
	
long long end,mj,p=1000000,stanga,dreapta,begin;	
		
int main()

{	
	fin>>n;
	for(i=0;i<n;i++)
	{ 	
		
		fin>>punct.x>>punct.y;
		v.push_back(punct);
	}
	
	
	
	
	sort(v.begin(),v.end(),compare);
	end=v[n-1].x;
	begin=v[0].x;
	long long mj=(begin+end)/2;
	rez1=Divide_and_Conquer(begin,mj,n);
	rez2=Divide_and_Conquer(mj+1,end,n);
	cout<<rez1<<" "<<rez2;
	if(rez1<rez2)
		rez2=rez1;
	else
		rez1=rez2;
	
	stanga=long (rez2);
	
	rez3=Divide_and_Conquer(mj-stanga,mj+stanga,n);
	cout<<" "<<rez3;
	fout << fixed << setprecision(6);
	if(rez3<rez1)
		fout<<rez3;
	else
		fout<<rez1;

	return 0;
}