Cod sursa(job #2189395)

Utilizator killer301Ioan Andrei Nicolae killer301 Data 28 martie 2018 10:20:14
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;

typedef pair <int, int> pii;

vector <pii> p;

double dist(pii a, pii b)
{
	return sqrt(1LL*(a.first - b.first) * (a.first - b.first) +
				1LL*(a.second - b.second) * (a.second - b.second));
}

bool cmp(pii a, pii b)
{
	return a.first < b.first || (a.first == b.first && a.second < b.second);
}

bool cmp2(pii a, pii b)
{
	return a.second < b.second || (a.second == b.second && a.first < b.first);
}

double solve(int st, int dr)
{
	double Min = 1e13;
	if(st == dr) return Min;
	if(dr == st+1) return dist(p[st], p[dr]);

	int mid = (st+dr)/2;
	vector <pii> v;
	double ymid = (p[mid].first + p[mid+1].second)/2;
	for(int i=mid; i>=st && abs(ymid - p[i].first) < Min; i--) v.push_back(p[i]);
	for(int i=mid+1; i<=dr && abs(ymid - p[i].first) < Min; i++) v.push_back(p[i]);

	sort(v.begin(), v.end(), cmp2);

	for(int i=0; i<v.size(); i++)
		for(int j=i+1; j<=i+4 && j<v.size(); j++)
			Min = min(Min, dist(v[i], v[j]));

	return Min;
}

int main()
{
	fstream in("cmap.in");
	fstream out("cmap.out");
    int n;
    in >> n;
    for(int i=0; i<n; i++)
	{
		int x, y;
		in >> x >> y;
		p.push_back(pii (x, y));
	}
	sort(p.begin(), p.end(), cmp);
	out << fixed << setprecision(12) << solve(0, n-1);
    return 0;
}