Cod sursa(job #3131643)

Utilizator tryharderulbrebenel mihnea stefan tryharderul Data 20 mai 2023 20:27:44
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.07 kb
#include <bits/stdc++.h>

using namespace std;

struct Point{ 
	double x, y; 
	bool operator<(const Point &other) {
		if(x == other.x) return y < other.y;
		return x < other.x;
	}
};

const pair<Point, Point> INF = {{-1e9, -1e9}, {1e9, 1e9}};
double dist(pair<Point, Point> a) { return 2LL * (a.first.x - a.second.x) * (a.first.x - a.second.x) + 2LL * (a.first.y - a.second.y) * (a.first.y - a.second.y); }

pair<Point, Point> min(pair<Point, Point> a, pair<Point, Point> b) { return (dist(a) < dist(b) ? a : b); }

pair<Point, Point> strip_solve(vector<Point> &points) {
	pair<Point, Point> ans = INF;
	for(int i = 0; i < (int)points.size(); i++)
		for(int j = i+1; j < i+7 && j < (int)points.size(); j++)
			ans = min(ans, {points[i], points[j]});
	return ans;
}

pair<Point, Point> solve(vector<Point> &points, int l, int r) {
	if(r-l <= 3) {
		pair<Point, Point> ans = INF;
		for(int i = l; i < r; i++)
			for(int j = i+1; j < r; j++)
				ans = min(ans, {points[i], points[j]});
		return ans;
	}
	
	int mid = (l+r) >> 1;
	pair<Point, Point> ans_left = solve(points, l, mid);
	pair<Point, Point> ans_right = solve(points, mid, r);
	pair<Point, Point> ans;
	 
	ans = min(ans_left, ans_right);
	double delta = dist(ans);
	
	Point mid_point = points[mid];
	vector<Point> strip;
	for(int i = l; i < r; i++)
		if(abs(points[i].x - mid_point.x) < delta)
			strip.push_back(points[i]);
			
	return min(ans, strip_solve(strip));
}

int main() {
	freopen("cmap.in", "r", stdin);
	freopen("cmap.out", "w", stdout);
	int n;
	scanf("%d", &n);
	vector<Point> v;
	for(int i = 0; i < n; i++) {
		double x, y;
		scanf("%lf %lf", &x, &y);
		v.push_back({x, y});
	}
	printf("%0.6lf\n", sqrt(dist(solve(v, 0, v.size()))));
	//~ int n;
	//~ while(scanf("%d", &n) && n > 0) {
		//~ vector<Point> v;
		//~ for(int i = 0; i < n; i++) {
			//~ double x, y;
			//~ scanf("%lf %lf", &x, &y);
			//~ v.push_back({x, y});
		//~ }
		//~ sort(v.begin(), v.end());
		//~ pair<Point, Point> ans = solve(v, 0, v.size());
		//~ printf("%0.2lf %0.2lf %0.2lf %0.2lf\n", ans.first.x, ans.first.y, ans.second.x, ans.second.y);
	//~ }
	
	return 0;
}