Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement