Cod sursa(job #1645946)

Utilizator tamionvTamio Vesa Nakajima tamionv Data 10 martie 2016 14:25:30
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.95 kb
#include <fstream>
#include <iomanip>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

struct punct{
	int x, y;	
	punct(){}
	punct(const int a, const int b): x(a), y(b){} };

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); }

struct x_cmp{
	bool operator()(const punct& a, const punct& b){
		return a.x < b.x; } };

struct y_cmp{
	bool operator()(const punct& a, const punct& b){
		return a.y < b.y; } };

struct x_part{
	double x;
	x_part(const double x_): x(x_){}
	bool operator()(const punct& a){
		return a.x < x; } };

double closest_points(vector<punct>& pts){
	// va lasa pts sortat dupa y
	if(pts.size() < 4){
		double rez = dist(pts[0], pts[1]);
		for(int i = 0; i < pts.size(); ++i){
			for(int j = i+1; j < pts.size(); ++j){
				rez = min(rez, dist(pts[i], pts[j])); } }
		sort(pts.begin(), pts.end(), y_cmp());
		return rez; }

	vector<punct>::iterator p_point = pts.begin() + pts.size()/2;
	nth_element(pts.begin(), p_point, pts.end(), x_cmp());

	const int x_mij = p_point -> x;

	vector<punct> pts_left(pts.begin(), p_point), pts_right(p_point, pts.end());

	const double rez_inter =
		min(closest_points(pts_left), closest_points(pts_right));
		
	merge(pts_left.begin(), pts_left.end(), pts_right.begin(), pts_right.end(),
		pts.begin(), y_cmp());

	vector<punct> strip;

	for(int i = 0; i < pts.size(); ++i){
		if(pts[i].x >= x_mij - rez_inter && pts[i].x <= x_mij + rez_inter){
			strip.push_back(pts[i]); } }

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

	return rez; }

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

	int n;
	f >> n;

	vector<punct> pts(n);
	for(int i = 0; i < n; ++i){
		f >> pts[i].x >> pts[i].y; }

	g << fixed << setprecision(7) << closest_points(pts);

	return 0; }