Cod sursa(job #2119729)

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

ll n,i,j,li,ls,rez;
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;	}

ll dis(pnct a,pnct b)
{
	ll x=abs(a.x-b.x), y=abs(a.y-b.y);
	return x*x+y*y;
}
ll cmap(ll st,ll dr)
{
	ll i,j,li,s=0,mx=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<=nre;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);
	
	rez=cmap(1,n);
	fout<<fixed<<setprecision(6)<<sqrt(rez)<<"\n";
}