Cod sursa(job #2975774)

Utilizator AlexNeaguAlexandru AlexNeagu Data 7 februarie 2023 15:00:54
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.46 kb
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

ifstream in("cmap.in");
ofstream out("cmap.out");

#define cin in 
#define cout out 

typedef long long ll;
const int MOD = 1e9 + 9;
const ll inf = 1e19;


struct P {
    int x, y;
    void read() {
        cin >> x >> y;
    }
    bool operator < (P him) {
        if(x == him.x) {
            return y < him.y;
        }
        return x < him.x;
    }
    void write() {
        cout << "(" << x << ' ' << y << ")\n";
    }
    pair<int, int> to_pair() {
        return make_pair(x, y);
    }
};

ll sqr(ll x) {
    return 1LL * x * x;
}

vector<P> points;
int n;

ll dist(const P &a, const P &b) {
    return sqr(a.x - b.x) + sqr(a.y - b.y);
}

bool check_dist(ll x1, ll x2, ll square_d) {
    return sqr(abs(x2 - x1)) < square_d;
}

ll solve(vector<P> &points, vector<P> &points_y) {
    if(points.size() <= 1) {
        return inf;
    }
    vector<P> left, right, left_y, right_y;
    int N = points.size();

    for(int i = 0; i < N; ++i) {
        if(i < N / 2) {
            left.push_back(points[i]);
        }
        else {
            right.push_back(points[i]);
        }
    }

    for(int i = 0; i < N; ++i) {
        if(points_y[i].to_pair() <= left.back().to_pair()) {
            left_y.push_back(points_y[i]);
        }
        else {
            right_y.push_back(points_y[i]);
        }
    }
    
    ll d1 = solve(left, left_y);
    ll d2 = solve(right, right_y);
    ll d = min(d1, d2);
    
    vector<P> all;
    for(int i = 0; i < N; ++i) {
        if(check_dist(points_y[i].x, left.back().x, d)) {
            all.push_back(points_y[i]);
        }
    }   

    for(int i = 0; i < (int) all.size(); ++i) {
        for(int j = i + 1; j < (int) all.size(); ++j) {
            if(!check_dist(all[i].y, all[j].y, d)) {
                break;
            }
            d = min(d, dist(all[i], all[j]));
        }
    }
    return d;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);    

    
    cin >> n;
    points.resize(n);

    for(int i = 0; i < n; ++i) {
        points[i].read();
    }

    vector<P> points_y(points.begin(), points.end());

    sort(points.begin(), points.end());
    sort(points_y.begin(), points_y.end(), [&] (P a, P b) {
        return a.y < b.y;
    });


    cout << fixed << setprecision(8) << sqrt(solve(points, points_y)) << '\n';
    return 0;
}