Cod sursa(job #2767844)

Utilizator OctavianVasileVasileOctavian OctavianVasile Data 8 august 2021 07:21:43
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <bits/stdc++.h>
#define N_MAX 100003
using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
pair <long long, long long> x [N_MAX], y [N_MAX], z [N_MAX];
int n;
long long distance (pair <long long, long long> a, pair <long long, long long> b) {
	return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}
long long bs (int st, int dr) {
	if (st >= dr)
		return LONG_MAX;
	if (dr - st + 1 == 2) {
		if (y [st] > y [st + 1]) {
			pair <long long, long long> var;
			var = y [st];
			y [st] = y [st + 1];
			y [st + 1] = var;
		}
		return distance (x [st], x [st + 1]);
	}
	int mij = (st + dr) / 2, cnt = 0;
	int i = st, j = mij + 1;
	long long ans = min (bs (st, mij), bs (mij + 1, dr));
	while (i <= mij && j <= dr){
		if (y [i] <= y[j])
			z [++ cnt] = y [i ++];
		else z [++ cnt] = y [j ++];
	}
	for (; i <= mij; i ++)
		z [++ cnt] = y [i];
	for (; j <= dr; j ++)
		z [++ cnt] = y [j];
	for (i = st; i <= dr; i ++)
		y [i] = z [i - st + 1];
	cnt = 0;
	for (i = st; i <= dr; i ++)
	if (abs (y [i].second - x [mij].first) <= ans)
		z [++ cnt] = y [i];
	for (int i = 1; i <= cnt; i ++)
	for (int j = i + 1; j <= cnt && j <= i + 7; j ++)
		ans = min (ans, distance (z [i], z [j]));
	return ans;
}

int main(){
	fin >> n;
	for (int i = 1; i <= n; i ++)
		fin >> x [i].first >> x [i].second;
	sort (x + 1, x + n + 1);
	for (int i = 1; i <= n; i ++) {
		y [i].second = x [i].first;
		y [i].first = x [i].second;
	}
	fout << setprecision(6) << fixed << sqrt (bs (1, n));
	return 0;
}