Cod sursa(job #3256768)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 16 noiembrie 2024 09:32:38
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long long ll;
typedef long double ld;
const ll INF=LLONG_MAX;
ll ans;
ll n;
struct point
{
	ll x,y;
} v[100005];
bool byy(point a,point b)
{
	return a.y<b.y;
}
ll dist(point a, point b)
{
	return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
void solve(int l,int r)
{
	if(l==r)
		return;
	int mij=(l+r)/2;
	ll xmid=v[mij].x;
	solve(l,mij);
	solve(mij+1,r);
	vector<point> vec;
	for(int i=l;i<=r;i++)
		if((v[i].x-xmid)*(v[i].x-xmid)<ans)
			vec.push_back(v[i]);
	sort(vec.begin(),vec.end(),byy);
	for(int i=0;i<vec.size();i++)	
		for(int j=i+1;j<vec.size();j++)
		{
			if((vec[i].y-vec[j].y)*(vec[i].y-vec[j].y)>=ans)
				break;
			ans=min(ans,dist(vec[i],vec[j]));
		}
}
int main()
{
	ios_base::sync_with_stdio(false);
	fin.tie(0);
	fin>>n;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		fin>>x>>y;
		v[i]={x,y};
	}
	ans=INF;
	solve(1,n);
	ld rez=ld(sqrtl(ans));
	fout<<fixed<<setprecision(12)<<rez;
	return 0;
}