Cod sursa(job #3203505)

Utilizator AlexMoto2006Motoasca Alexandru-Lucian AlexMoto2006 Data 13 februarie 2024 19:51:23
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <fstream>
#include <vector>
#include <set>
#include <cmath>
#include <limits>
#include <algorithm>
using namespace std;

int n,m;

struct coord {
	int x, y;
	bool operator<(const coord& other) const {
		if (x != other.x) {
			return x < other.x;
		}
		return y < other.y;
	}
};

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

bool xcmp(const coord& a, const coord& b) {
	return a.x < b.x;
}	

bool ycmp(const coord& a, const coord& b) {
	return a.y < b.y;
}

double calculateDistance(const coord& a, const coord& b) {
	return sqrt((a.x - b.x) * 1ll * (a.x - b.x) + (a.y - b.y) * 1ll * (a.y - b.y));
}

double closestPairSweep(vector<coord>& v) {
	double minDistance = numeric_limits<double>::max();
	set<coord> s;
	s.insert(v[1]);
	int left = 1;
	for (int i = 2; i <= n; i++) 
	{
		while (v[i].x - v[left].x > minDistance && left<i) 
		{
			s.erase(v[left]);
			left++;
		}
		auto it = s.lower_bound({ static_cast<int>(v[i].y - minDistance), v[i].x});
		while (it != s.end() && it->y - v[i].y < minDistance) 
		{
			minDistance = min(minDistance, calculateDistance(v[i], *it));
			it++;
		}
		s.insert(v[i]);
	}
	return minDistance;
}

int main()
{
	cin >> n;

	vector<coord> v(n+1);
	for (int i = 1; i <= n; i++)
	{	
		cin >> v[i].x >> v[i].y;
	}
	sort(v.begin() + 1, v.end(), xcmp);

	cout.precision(8);
	cout << closestPairSweep(v);
	return 0;
}