Cod sursa(job #2499008)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 25 noiembrie 2019 08:34:51
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

#define int long long

const int INF = 1e18;

vector <pair <int, int> > points;

int sq(int x)
{
	return x * x;
}

int dist(pair <int, int> A, pair <int, int> B)
{
	return (sq(A.first - B.first) + sq(A.second - B.second));
}

int solve(int l, int r)
{
	if(r - l <= 3)
	{
		int res = INF;
		
		for(int i = l; i < r; i++)
			for(int j = i + 1; j <= r; j++)
				res = min(res, dist(points[l], points[r]));
		
		return res;
	}
	
	int mid = (l + r) / 2;
	int d = min(solve(l, mid), solve(mid + 1, r));
	
	vector <pair <int, int> > aux;
	
	for(int i = l; i <= r; i++)
		if(abs(points[mid].first - points[i].first) <= d)
			aux.push_back({points[i].second, points[i].first});
	
	sort(aux.begin(), aux.end());
	
	for(int i = 0; i < aux.size(); i++)
		for(int j = i + 1; j < aux.size() && j - i < 8; j++)
			d = min(d, dist(aux[i], aux[j]));
	
	return d;
}

main()
{
	 int n;
	 fin >> n;
	 
	 for(int i = 1; i <= n; i++)
	 {
		 int x, y;
		 fin >> x >> y;
		 
		 points.push_back({x, y});
	 }
	 
	 sort(points.begin(), points.end());
	 
	 fout << fixed << setprecision(7) << sqrt(1.0 * solve(0, n - 1)) << '\n';
}