Cod sursa(job #2857079)

Utilizator cristia_razvanCristia Razvan cristia_razvan Data 24 februarie 2022 20:35:59
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define dbg(i) (cout<<#i<<" = "<<(i)<<'\n')

using ll = long long;
using ui = unsigned int;



const string fn = "cmap";

ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

#define x first
#define y second

using point = pair <int , int>;

vector<point>a;

int n;

bool cmpp(point p1, point p2) {
	return p1.y < p2.y;
}

double dist(point p1, point p2) {
	return sqrt((p1.x - p2.x) * (p1.x - p2.x) +
	            (p1.y - p2.y) * (p1.y - p2.y));
}

double brute(int st, int dr) {
	double mn = DBL_MAX;
	for (int i = st; i < dr; ++i)
		for (int j = i + 1; j <= dr; ++j)
			if (dist(a[i], a[j]) < mn)
				mn = dist(a[i], a[j]);
	return mn;
}

/// cu sort

double intre(vector <point> b, double d) {

	double mn = d;
	sort(b.begin(), b.end(), cmpp);
	for (int i = 0; i < b.size(); ++i)
		for (int j = i + 1; j < b.size() && (b[j].y - b[i].y) < mn; ++j)
			mn = dist(b[i], b[j]);
	return mn;
}

double daq(int st, int dr) {

	int ac_n;
	if (dr - st + 1 <= 3)
		return brute(st, dr);
	int mid = (st + dr) >> 1;
	point midPoint = a[mid];

	double dL = daq(st, mid);
	double dR = daq(mid + 1, dr);

	double d = min(dL, dR);

	vector<point> b;
	for (int i = st; i <= dr; ++i) {
		if (abs(a[i].x - midPoint.x) < d)
			b.pb(a[i]);
	}
	return min(d, intre(b, d));

}

int main() {

	fin >> n;
	a.resize(n + 1);
	for (int i = 1; i <= n; ++i)
		fin >> a[i].first >> a[i].second;

	sort(a.begin() + 1, a.end());

	fout << fixed << setprecision(7) << daq(1, n) << '\n';

	fin.close();
	fout.close();
	return 0;
}