Cod sursa(job #2661948)

Utilizator akumariaPatrascanu Andra-Maria akumaria Data 22 octombrie 2020 23:57:01
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.84 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

struct point {
	long long x, y;
};

vector<point> points;

bool comp (const point a, const point b) {
	if (a.x < b.x)
		return 0;
	if (a.x > b.x)
		return 1;

	if (a.y < b.y)
		return 0;
	if (a.y > b.y)
		return 1;

	return 0;
}


long long euclid_distance(const point &a, const point &b) {
	return (a.x - b. x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}


long long min(long long a, long long b) {
	return a < b? a:b;
}



long long divide_et_impera(int left, int right) {
	if (right - left <= 2) {
		long long res = euclid_distance(points[left], points[right]);
		if (right - left == 1)
			return res;

		return min(res, min(euclid_distance(points[left], points[left + 1]), euclid_distance(points[left+1], points[right])));

	}

	long long left_res = divide_et_impera(left, (left + right) / 2);
	long long right_res = divide_et_impera((left + right) / 2 + 1, right);

	long long current_res = min(right_res, left_res);
	long long dividing_line = (points[(left + right) / 2].x + points[(left + right) / 2 + 1].x) / 2;

	for(int i = (left + right) / 2 - 3; i<= (left + right) / 2; ++i)
		if (i >= left && points[i].x > dividing_line - current_res)
			for(int j = (left + right) / 2 + 4; j> (left + right) / 2; --j)
				if (j <= right && points.size() && points[j].x < dividing_line + current_res)
					current_res = min(current_res, euclid_distance(points[i], points[j]));

	return current_res;
}


int main() {
	freopen("cmap.in", "r", stdin);
	freopen("cmap.out", "w", stdout);

	int n;
	scanf("%d", &n);
	points.resize(n);
	for(int i=0; i<n; ++i)
		scanf("%lld%lld", &points[i].x, &points[i].y);


	sort(points.begin(), points.end(), comp);
	printf("%.6f\n", sqrt(divide_et_impera(0, n-1)));

	return 0;
}