Cod sursa(job #2883559)

Utilizator ptudortudor P ptudor Data 1 aprilie 2022 16:47:32
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include <bits/stdc++.h>
#define dbg(x) if (COND) {cout << #x << "=" << x << "\n"; }
#define dbgvp(x) if (COND) {cout << #x << ": "; for (auto k : x) {cout << "{" << k.first << "," << k.second << "} "; }cout << "\n";}
#define sep if(COND) cout << "\n-------------------------\n";
#define dbgp(x) if (COND) {cout << #x << "={" << x.first << "," << x.second << "}\n";}
using namespace std;
bool COND = true;

#ifdef LOCAL
ifstream in("in.in");
ofstream out("out.out");
#else
ifstream in("cmap.in");
ofstream out("cmap.out");
#endif // LOCAL

typedef pair<int,int> pp;

int n;
vector<pp> pt;

double modulo(double x) {
    if ( x > 0) return x;
    return -x;
}
double sq(double x) {
    return x * x;
}
double dist(pp A, pp B) {
    return sqrt( sq( A.first - B.first ) + sq(A.second - B.second ) );
}
double solve(int l, int r) {
    if (r - l + 1 <= 1) {
        return 1 / .0;
    }
    int mid = (l + r) / 2;
    int midx = pt[mid].first; ///any points on the line are in the first half
   // dbg(mid);
   // dbg(midx);
    double s = min(solve(l , mid) , solve(mid + 1 , r));
    //dbg(s);
/*
    if (l == 1 && r == n) {
        dbg(mid);
        dbg(solve(l , mid));
        dbg(solve(mid + 1 , r));
        dbg(s);

    }*/

    vector<pair<int,int>> y;

    for (int i = l; i <= r; i++) {
        if ( modulo(midx - pt[i].first) <= s) {
            y.push_back(pt[i]);
        }
    }
    sort(y.begin(), y.end() , [&](pp A, pp B) {
            return A.second < B.second;
        }
    );
   // dbgvp(y);

    for (int i = 0; i < y.size(); i++) {
        for (int j = i + 1; j < min((int)y.size() , i + 8); j++ ) {
            s = min(s , dist(y[i] , y[j]));
           // dbg(i);
           // dbg(j);
           // dbgp(y[i]);
          //  dbgp(y[j]);
          //  dbg(dist(y[i] , y[j]));
          //  dbg(s);
          //  sep;
        }
    }

   // i//f ( l == 1 && r == n) {
      //  dbg(s);

    //}

    return s;
}

int main() {
    in >> n;
    pt.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        int x,y;
        in >> x >> y;
        pt[i] = {x,y};
    }
    sort(pt.begin() + 1, pt.end());///sort after x

   // dbgvp(pt);
    out << fixed << setprecision(12) << solve(1 , n) << "\n";
}