Cod sursa(job #3243314)

Utilizator hhhhhhhAndrei Boaca hhhhhhh Data 17 septembrie 2024 15:18:47
Problema Cele mai apropiate puncte din plan Scor 95
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
typedef long double ld;
typedef long long ll;
const ll INF=LONG_LONG_MAX;
ll n,ans;
struct point
{
	ll x,y;
} v[100005];
bool byx(point a,point b)
{
	return a.x<b.x;
}
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(ll st,ll dr)
{
	if(st==dr)
		return;
	ll mij=(st+dr)/2;
	solve(st,mij);
	solve(mij+1,dr);
	vector<point> p;
	for(int i=st;i<=dr;i++)
		if((v[i].x-v[mij].x)*(v[i].x-v[mij].x)<=ans)
			p.push_back(v[i]);
	for(int i=0;i<p.size();i++)
		for(int j=i+1;j<p.size();j++)
		{
			if((p[i].x-p[j].x)*(p[i].x-p[j].x)>ans)
				break;
			ll d=dist(p[i],p[j]);
			/*if(d==0)
				cout<<p[i].x<<' '<<p[i].y<<' '<<p[j].x<<' '<<p[j].y<<'\n';*/
			ans=min(ans,dist(p[i],p[j]));
		}
}
int main()
{
	ios_base::sync_with_stdio(false);
	fin.tie(0);
	fin>>n;
	for(int i=1;i<=n;i++)
		fin>>v[i].x>>v[i].y;
	sort(v+1,v+n+1,byx);
	ans=INF;
	solve(1,n);
	ld rez=(ld)sqrtl(ans);
	fout<<fixed<<setprecision(10)<<rez;
	return 0;
}