Cod sursa(job #2366678)

Utilizator patcasrarespatcas rares danut patcasrares Data 4 martie 2019 21:31:46
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include<fstream>
#include<vector>
#include<stack>
#include<iomanip>
#include<climits>
#include<limits>
#include<cmath>
#define x first
#define y second
#define pb push_back
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int DN=1e5+5;
int n;
typedef pair<int,int> pii;
pii a[DN],b[DN],r[DN];
long long rez;
double sol;
long long dist(pii A,pii B)
{
	return 1LL*(A.x-B.x)*(A.x-B.x)+1LL*(A.y-B.y)*(A.y-B.y);
}
void solve(int st,int dr)
{
	if(st==dr)
		return;
	int mij=(st+dr)/2,ls=st,ld=mij+1,pz=st,m=0;
	solve(st,mij);
	solve(mij+1,dr);
	for(int i=st;i<=dr;i++)
	{
		if(ls>mij||(ld<=dr&&a[ld].y<a[ls].y))
		{
			b[pz]=a[ld];
			ld++;
			pz++;
			continue;
		}
		b[pz]=a[ls];
		pz++;
		ls++;
	}
	for(int i=st;i<=dr;i++)
	{
		a[i]=b[i];
		if(abs(a[i].x-a[mij].x)<=rez)
		{
			m++;
			r[m]=a[i];
		}
	}
	for(int i=1;i<=m;i++)
		for(int j=i+1;j<=min(m,i+7);j++)
			rez=min(rez,dist(r[i],r[j]));
}
int main()
{
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>a[i].x>>a[i].y;
	rez=numeric_limits<long long>::max();
	solve(1,n);
	sol=rez;
	sol=sqrt(sol);
	fout<<fixed<<setprecision(7)<<sol;
}