Cod sursa(job #2489328)

Utilizator richard26Francu Richard richard26 Data 8 noiembrie 2019 15:41:13
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
#include <bits/stdc++.h>

using namespace std;

bool cmp_y(pair <double, double> p1, pair <double, double> p2) {
	return p1.second < p2.second;
}

double distance(pair <double, double> p1, pair <double, double> p2) {
	return sqrt(pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2) );
}

double merge(int left, int mid, int right, vector <pair<double, double> > points, double min_dist) {

	vector <pair <double, double> > new_points;

	for (int i = left; i <= right; i++) {
		{
			if (points[i].first < points[mid].first + min_dist && points[i].first > points[mid].first - min_dist) {
				new_points.push_back(points[i]);
			}
		}
	}

	sort(new_points.begin(), new_points.end(), cmp_y);
	double dist = min_dist;

	for (int i = 0; i < new_points.size(); i++) {
		for (int j = 1; j < 9 && (i + j) < new_points.size(); j++) {

			dist = min(dist, distance(new_points[i], new_points[i + j]));
		}
	}

	return dist;

}

double divide(int left, int right, vector < pair <double, double> > points) {

	if (right - left + 1 <= 3) {

		double min_dist = numeric_limits<double>::max();

		for (int i = left; i < right; i++) {

			for (int j = i + 1; j <= right; j++) {	

				double curr_dist = distance(points[i], points[j]);
				if (curr_dist < min_dist) {
					min_dist = curr_dist;
				}
			}
 		}

 		return min_dist;
	}

	int mid = (left + right) / 2;
	double min_dist_left = divide(left, mid, points);
	double min_dist_right = divide(mid, right, points);

	double min_dist = (min_dist_left < min_dist_right) ? min_dist_left:min_dist_right;
	min_dist = min (merge(left, mid, right, points, min_dist), min_dist) ;

	return min_dist;

}


int main()
{
	ifstream f("cmap.in");
	ofstream g("cmpa.out");
	int n;
	vector< pair<double, double> > points;

	f >> n;
	for (int i = 0; i < n; i++) {
		pair <double, double> read;
		f >> read.first >> read.second;
		points.push_back(read);
	}

	sort(points.begin(), points.end());

	g << setprecision(6) << divide(0, n, points) << "\n";

	return 0;

}