Pagini recente » Cod sursa (job #1285426) | Cod sursa (job #3181794) | Cod sursa (job #1418884) | Cod sursa (job #1317933) | Cod sursa (job #2377729)
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-10;
double minimum (double a, double b) {
if (a + eps <= b) return a;
return b;
}
double sq (double x) {
return x * x;
}
double getDistance (pair <double, double> &A, pair <double, double>& B) {
return sqrt (sq(A.first - B.first) + sq(A.second - B.second));
}
double getDistance (vector <pair <double, double>> &points) {
if (points.size() <= 3) {
for (auto &x : points) {
swap (x.first, x.second);
}
sort (points.begin(), points.end());
for (auto &x : points) {
swap (x.first, x.second);
}
double minim = 1e15;
for (int i = 0; i < points.size(); ++i) {
for (int j = i + 1; j < points.size(); ++j) {
minim = minimum(minim, getDistance(points[i], points[j]));
}
}
return minim;
}
vector <pair <double, double>> left, right;
int middle = points.size() / 2;
for (int i = 0; i <= middle; ++i) {
left.push_back(points[i]);
}
for (int j = middle + 1; j < points.size(); ++j) {
right.push_back(points[j]);
}
double minim = getDistance(left);
minim = minimum (minim, getDistance(right));
points.clear();
reverse(left.begin(), left.end());
reverse(right.begin(), right.end());
while (left.size() || right.size()) {
if (left.empty() || (right.size() and right.back().second + eps <= left.back().second)) {
points.push_back(right.back());
right.pop_back();
}
else {
points.push_back(left.back());
left.pop_back();
}
}
for (int i = 0; i < points.size(); ++i) {
for (int j = i + 1; j < min((int)points.size(), i + 8); ++j) {
minim = minimum(minim, getDistance(points[i], points[j]));
}
}
return minim;
}
int main() {
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
ios::sync_with_stdio(false);
fin.tie(nullptr);
vector <pair <double, double>> points;
int n;
fin >> n;
for (int i = 1; i <= n; ++i) {
double x, y;
fin >> x >> y;
points.emplace_back(x, y);
}
sort (points.begin(), points.end());
fout << setprecision(7) << fixed << getDistance(points);
return 0;
}