Cod sursa(job #2046406)

Utilizator bt.panteaPantea Beniamin bt.pantea Data 23 octombrie 2017 19:46:38
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include <bits/stdc++.h>
#define ll long long
#define NMAX 100005
#define pr pair<int, int>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");

inline ll dist(int a, int b, pr v[])
{
	return (v[a].first - v[b].first) * (v[a].first - v[b].first) + (v[a].second - v[b].second) * (v[a].second - v[b].second);
}

inline ll distPr(pr a, pr b)
{
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}


ll dei(int left, int right, pr v[])
{
	if(right - left == 2)
		return dist(left, left + 1, v);
	else if (right - left == 3)
		return min(dist(left, left + 1, v), min(dist(left, left + 2, v), dist(left + 1, left + 2, v)));
	vector<pr> w;
	int mid = (left + right) / 2;
	ll best = min(dei(left, mid, v), dei(mid, right, v));
	int y = v[mid].first;
	int k = 0;
	for (int i = left; i < right; i++)
		if (abs(v[i].first - v[mid].first) <= best)
			w.push_back(v[i]);
	for(unsigned i = 0; i < w.size(); i++)
		for(unsigned j = 1; i + j < w.size() && j <= 8; j++)
			best = min(distPr(w[i], w[i + j]), 1LL * best);
	return best;
}

int main()
{
	pair<int, int> v[NMAX];
	int n;
	f>>n;
	for(int i = 0; i < n; i++)
		f>>v[i].first>>v[i].second;
	sort(v, v + n);
	g<<fixed<<setprecision(6)<<sqrt(dei(0, n, v));
	return 0;
}