Pagini recente » Profil usureluflorian | Rating LIIS Moisil Aruxandei Romanescu Iordan (AruxandeiRomanescuIordan) | Cod sursa (job #456498) | Cod sursa (job #3150562) | Cod sursa (job #3203506)
#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("cmap.in");
ofstream cout("cmap.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;
}