Cod sursa(job #2119528)

Utilizator shantih1Alex S Hill shantih1 Data 1 februarie 2018 13:20:27
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");

double s;
int n,i,j,li,ls;
struct pnct
{	int x,y;	}	p[100005], yul[100005];

bool cord(pnct x,pnct y)
{	return x.y<y.y;	}
bool cabs(pnct x,pnct y)
{	return x.x<y.x;	}

double dis(pnct a,pnct b)
{
	int x=abs(a.x-b.x), y=abs(a.y-b.y);
	return sqrt(x*x+y*y);
}
double cmap(int st,int dr)
{
	int i,j,li;
	double s=0.0,mx=0.0;
	if(dr-st<3)
	{
		mx=dis(p[st],p[st+1]);
		for(i=st;i<dr;i++)
			for(j=i+1;j<=dr;j++)
			{
				s=dis(p[i],p[j]);
				if(s<mx)	mx=s;
			}
		return mx;
	}
	li=(st+dr)/2;
	mx=cmap(st,li);
	mx=min(mx,cmap(li+1,dr));
	
	pnct ox[dr-st+1];
	int dd=p[li].x,nre=0;
	for(i=st;i<=dr;i++)
		if(double(abs(yul[i].x-dd))<=s)
		{
			nre++;
			ox[nre]=yul[i];
		}
	for(i=1;i<nre;i++)
		for(j=i+1;j<=i+7;j++)
		{
			s=dis(ox[i],ox[j]);
			if(s<mx)	mx=s;
		}
	return mx;
}

int main () {
	
	fin>>n;
	for(i=1;i<=n;i++)
	{
		fin>>p[i].x>>p[i].y;
		yul[i]=p[i];
	}
	sort(p+1,p+n+1,cabs);
	sort(yul+1,yul+n+1,cord);
	
	fout<<setprecision(6)<<fixed<<cmap(1,n)<<"\n";
}