Cod sursa(job #1721104)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 24 iunie 2016 15:06:19
Problema Cele mai apropiate puncte din plan Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.76 kb
#include <bits/stdc++.h>
using namespace std;

struct punct{
	double x, y; };

double dist(const punct& p1, const punct& p2){
	return hypot(p1.x-p2.x, p1.y-p2.y); }

struct cmap_rez_t {
	vector<punct> by_y;
	double dist; };

auto cmp_by_y = [](const punct& p1, const punct& p2){
	return p1.y < p2.y; };

cmap_rez_t cmap(vector<punct>& v){

	if(v.size() < 10){
		double rez = dist(v[0], v[1]);
		for(int i = 0; i < v.size(); ++i){
			for(int j = i+1; j < v.size(); ++j){
				rez = min(rez, dist(v[i], v[j])); } }

		sort(begin(v), end(v), cmp_by_y);
		return cmap_rez_t { move(v), rez }; }

	const int n = v.size();
	nth_element(begin(v), begin(v) + n/2, end(v), [](const punct& p1, const punct& p2){
			return p1.x < p2.x; });
	const double mid = v[n/2].x;

	vector<punct> left, right;
	auto tmp = [mid](const punct& p){ return p.x < mid; };

	copy_if(begin(v), end(v), back_inserter(left), tmp);
	v.erase(remove_if(begin(v), end(v), tmp), end(v));
	right = move(v);

	auto rez_left = cmap(left), rez_right = cmap(right);

	vector<punct> by_y;
	
	merge(begin(rez_left.by_y), end(rez_left.by_y), begin(rez_right.by_y), end(rez_right.by_y), back_inserter(by_y),
			cmp_by_y);

	vector<punct> fasie;

	double rez = min(rez_left.dist, rez_right.dist);

	copy_if(begin(by_y), end(by_y), back_inserter(fasie), [mid, rez](const punct& p1){
			return mid-rez <= p1.x && p1.x <= mid+rez; });

	for(int i = 0; i < fasie.size(); ++i){
		for(int j = i-1; j >= 0 && abs(fasie[i].y-fasie[j].y) <= rez; --j){
			rez = min(rez, dist(fasie[i], fasie[j])); } }

	return cmap_rez_t { move(by_y), rez }; }

int main(){
	ifstream f("cmap.in");
	ofstream g("cmap.out");
	int n;

	f >> n;

	vector<punct> v(n);
	for(auto& p : v){
		f >> p.x >> p.y; }

	g << fixed << setprecision(6) << cmap(v).dist << endl;

	return 0; }