Cod sursa(job #2489429)

Utilizator richard26Francu Richard richard26 Data 8 noiembrie 2019 19:27:52
Problema Cele mai apropiate puncte din plan Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <bits/stdc++.h>

using namespace std;

typedef pair <long long, long long> point;

const long long INF = 1e18;

vector <point> points;

long long distance(point p1, point p2) {

	return (p1.first - p2.first) * (p1.first - p2.first) + (p1.second - p2.second) * (p1.second - p2.second);
}

bool cmp_y(point p1, point p2) {
	return p1.second <= p2.second;
}

long long merge(long long dist, int left, int right) {

	int mid = (left + right) / 2;
	vector <point> new_points;
	long long min_dist = INF;

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

	sort(new_points.begin(), new_points.end(), cmp_y);

	for (int i = 0; i < new_points.size(); i++) {

		for (int j = i + 1; j < i + 8 && j < new_points.size(); j++) {
			min_dist = min(min_dist, distance(points[i], points[j]));
		}
	}

	return min_dist;
}

long long divide(int left, int right) {

	if (right - left < 2) {

		if (right - left == 0) {
			return INF;
		}

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

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

				min_dist = min(min_dist, distance(points[i], points[j]) );
			}
		}

		return min_dist;
		
	}
		

	int mid = (left + right) / 2;
	long long min_dist_left = divide(left, mid);
	long long min_dist_right = divide(mid + 1, right);

	long long min_dist = min(min_dist_left, min_dist_right);

	min_dist = (merge(min_dist, left, right), min_dist) ;
	return min_dist;
}

int main()
{

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

	int n;
	f >> n;

	for (int i = 0; i < n; i++) {

		point read;

		f >>  read.first >> read.second;
		points.push_back(read);
	}

	sort (points.begin(), points.end());
	g << fixed << setprecision(9) << sqrt((double) divide(0, n - 1));

	return 0;
}