Cod sursa(job #3340405)

Utilizator andrei.nNemtisor Andrei andrei.n Data 14 februarie 2026 10:33:59
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.31 kb
#include <bits/stdc++.h>

using namespace std;

#ifndef LOCAL
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
#define cin fin
#define cout fout
#endif

struct Vec2 {
    double x, y;
    Vec2(double _x = 0, double _y = 0) : x(_x), y(_y) {}
};

inline Vec2 operator+(Vec2 a, Vec2 b) {return Vec2(a.x + b.x, a.y + b.y);}
inline Vec2 operator-(Vec2 a, Vec2 b) {return Vec2(a.x - b.x, a.y - b.y);}
inline Vec2 operator*(Vec2 a, double b) {return Vec2(a.x * b, a.y * b);}
inline Vec2 operator/(Vec2 a, double b) {return Vec2(a.x / b, a.y / b);}
inline Vec2 &operator+=(Vec2 &a, Vec2 b) {return a = a + b;}
inline Vec2 &operator-=(Vec2 &a, Vec2 b) {return a = a - b;}
inline Vec2 &operator*=(Vec2 &a, double b) {return a = a * b;}
inline Vec2 &operator/=(Vec2 &a, double b) {return a = a / b;}

inline double abs(Vec2 v) {return sqrt(v.x * v.x + v.y * v.y);}
inline double cross(Vec2 a, Vec2 b) {return a.x * b.y - a.y * b.x;}
inline double dot(Vec2 a, Vec2 b) {return a.x * b.x + a.y * b.y;}
inline Vec2 norm(Vec2 v) {return v / abs(v);}

void read(Vec2 &v) {
    cin>>v.x>>v.y;
}

const int BULAN = 7;

double sneakySolve(vector<Vec2> v) {
    if(v.size() <= 1) {
        return 1e15;
    } else if(v.size() == 2) {
        return abs(v[0] - v[1]);
    } else if(v.size() == 3) {
        return min(abs(v[0] - v[1]), min(abs(v[0] - v[2]), abs(v[1] - v[2])));
    }
    sort(v.begin(), v.end(), [](Vec2 a, Vec2 b){return a.x < b.x;});
    int c1 = v.size() / 2;
    double d = v[c1 - 1].x - 0.5;
    vector<Vec2> sneaky1(v.begin(), v.begin() + c1);
    vector<Vec2> sneaky2(v.begin() + c1, v.end());
    double ans = min(sneakySolve(sneaky1), sneakySolve(sneaky2));
    vector<Vec2> lst;
    for(Vec2 i : v) {
        if(abs(i.x - d) <= ans) {
            lst.push_back(i);
        }
    }
    sort(lst.begin(), lst.end(), [](Vec2 a, Vec2 b){return a.y < b.y;});
    for(int i=0; i<lst.size(); ++i) {
        for(int j=i+1; j<lst.size() && j <= i + BULAN; ++j) {
            ans = min(ans, abs(lst[i] - lst[j]));
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n; cin>>n;
    vector<Vec2> v(n);
    for(int i=0; i<n; ++i) {
        read(v[i]);
    }
    cout << fixed << setprecision(8) << sneakySolve(v);
    return 0;
}