Cod sursa(job #2868866)

Utilizator JaguarKatStere Teodor Ioanin JaguarKat Data 11 martie 2022 11:10:12
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <bits/stdc++.h>

using namespace std;

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

const long long INF = 4e18;

vector<pair<long long, long long>> x, y;
vector<pair<long long, long long>> v(100005);

long long dst(pair<long long, long long> a, pair<long long, long long> b)
{
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

long long rez(int st, int dr, vector<pair<long long, long long>> &xx, vector<pair<long long, long long>> &yy)
{
	if(st >= dr - 1)return INF;
	else if(dr - st == 2)
	{
		if(yy[st] > yy[st + 1])swap(yy[st], yy[st + 1]);
		return dst(xx[st], xx[st + 1]);
	}
	int mij = (st + dr) / 2;
	long long sol = min(rez(st, mij, xx, yy), rez(mij, dr, xx, yy));
	merge(yy.begin() + st, yy.begin() + mij, yy.begin() + mij, yy.begin() + dr, v.begin());
	copy(v.begin(), v.begin() + (dr - st), yy.begin() + st);
	int ind = 0;
	for(int i = st; i < dr; ++i)if(abs(yy[i].second - xx[mij].first) <= sol)v[ind++] == yy[i];
	for(int i = 0; i < ind - 1; ++i)for(int j = i + 1; j < ind and j - i < 8; ++j)sol = min(sol, dst(v[i], v[j]));
	return sol;
}


int main()
{
	int n;
	fin >> n;
	x.resize(n);
	y.resize(n);
	for(int i = 0; i < n; ++i)fin >> x[i].first >> x[i].second;
	sort(x.begin(), x.end());
	for(int i = 0; i < n; ++i)y[i] = {x[i].second, x[i].first};
	fout << fixed << setprecision(6) << sqrt(rez(0, n, x, y)) << '\n';
	return 0;
}