Pagini recente » Cod sursa (job #2087035) | Cod sursa (job #812575) | Cod sursa (job #195112) | Cod sursa (job #2356586) | Cod sursa (job #2699550)
#include <bits/stdc++.h>
#define int long long
#define sqr(x) ((x) * (x))
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
class point {
public:
int x, y;
};
int dist(const point &p1, const point &p2) {
return sqr(p1.x - p2.x) + sqr(p1.y - p2.y);
}
int smallest_distance(const vector<point> &points, const vector<point> &points_by_y) {
int N = points.size();
if(N < 2)
return 9e18L;
vector<point> left = vector<point>(points.begin(), points.begin() + N / 2),
right = vector<point>(points.begin() + N / 2, points.end());
vector<point> left_by_y, right_by_y;
for(const point &p : points_by_y)
if(make_pair(p.x, p.y) <= make_pair(left.back().x, left.back().y))
left_by_y.emplace_back(p);
else
right_by_y.emplace_back(p);
int d1 = smallest_distance(left, left_by_y),
d2 = smallest_distance(right, right_by_y),
d = min(d1, d2);
int middle_x = left.back().x;
vector<point> stripe;
for(const point &p : points_by_y)
if(sqr(p.x - middle_x) < d)
stripe.emplace_back(p);
int M = stripe.size();
for(int i = 0; i < M; ++i) {
// Lemma: Complexitatea celui de-al doilea for este O(1)
for(int j = i + 1; j < M && sqr(stripe[j].y - stripe[i].y) < d; ++j)
d = min(d, dist(stripe[i], stripe[j]));
}
return d;
}
void test_case() {
int N;
fin >> N;
vector<point> points(N);
for(point &p : points)
fin >> p.x >> p.y;
sort(points.begin(), points.end(), [&](const point &A, const point &B) -> bool {
return make_pair(A.x, A.y) < make_pair(B.x, B.y);
});
vector<point> y_sorted = points;
sort(y_sorted.begin(), y_sorted.end(), [&](const point &A, const point &B) -> bool {
return A.y < B.y;
});
fout << fixed << setprecision(8) << sqrtl(smallest_distance(points, y_sorted)) << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
while(T--)
test_case();
}