Cod sursa(job #1537785)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 28 noiembrie 2015 00:00:25
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.8 kb
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

struct punct{ double x, y; };

auto by_x = [](const punct& a, const punct& b){
	return a.x < b.x || (a.x == b.x && a.y < b.y); };

auto by_y = [](const punct& a, const punct& b){
	return a.y < b.y || (a.y == b.y && a.x < b.x); };

double dist(const punct& a, const punct& b){
	const double dx = a.x - b.x, dy = a.y - b.y;
	return sqrt(dx*dx + dy*dy); }

double cmap(const vector<punct>& pts, int st, int dr, vector<punct>& pts_by_y){
	if(dr-st+1 <= 3){
		pts_by_y.resize(dr-st+1);
		copy(begin(pts)+st, begin(pts)+dr+1, begin(pts_by_y));
		sort(begin(pts_by_y), end(pts_by_y), by_y);

		double rez = 2e9;
		for(int i = st; i <= dr; ++i){
			for(int j = i+1; j <= dr; ++j){
				rez = min(rez, dist(pts[i], pts[j])); } }
		return rez; }
	const int mij = st + (dr-st+1)/2;
	vector<punct> pts_by_y_st, pts_by_y_dr;
	const double rez_st = cmap(pts, st, mij, pts_by_y_st), rez_dr = cmap(pts, mij+1, dr, pts_by_y_dr);
	double rez = min(rez_st, rez_dr);
	pts_by_y.resize(dr-st+1);
	merge(begin(pts_by_y_st), end(pts_by_y_st), begin(pts_by_y_dr), end(pts_by_y_dr),
		begin(pts_by_y), by_y);

	vector<punct> pts_mijloc;
	copy_if(begin(pts_by_y), end(pts_by_y), back_inserter(pts_mijloc),
		[&pts, mij, rez](const punct& p){ return abs(p.x - pts[mij].x) <= rez; });

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

int main(){
	ifstream f("cmap.in");
	ofstream g("cmap.out");
	int n;
	f >> n;
	vector<punct> pts(n);
	for(auto& p : pts){
		f >> p.x >> p.y; }
	sort(begin(pts), end(pts), by_x);
	vector<punct> pts_by_y;
	g << fixed << setprecision(6) << cmap(pts, 0, n-1, pts_by_y);
	return 0; }