Cod sursa(job #2921951)

Utilizator tzancauraganuTzanca Uraganu tzancauraganu Data 2 septembrie 2022 16:43:28
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.3 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <cassert>
#include <cstring>
#include <set>
#include <unordered_map>
#include <memory>
#include <deque>
#include <queue>
#include <iomanip>
#include <algorithm>
#include <cmath>
 
using namespace std;


ifstream f("cmap.in");
ofstream g("cmap.out");
 
const double EPS = 1e-7;

struct Pt {
    int x, y;

    Pt(): x(0), y(0) {}
    Pt(int x_, int y_): x(x_), y(y_) {}
};

bool cmpPtByX(const Pt& a, const Pt& b) {return a.x != b.x ? a.x < b.x : a.y < b.y;}
bool cmpPtByY(const Pt& a, const Pt& b) {return a.y != b.y ? a.y < b.y : a.x < b.x;}

long long dist(const Pt& a, const Pt& b) {
    return 1LL * (a.x - b.x) * (a.x - b.x) + 1LL * (a.y - b.y) * (a.y - b.y);
}

void add(deque<Pt>& S, const Pt& n, long long& mind) {
    while (S.size() >= 7)
        S.pop_front();
    
    for (const auto& p : S)
        mind = min(mind, dist(p, n));
    S.push_back(n);
}

long long solve(const vector<Pt>::iterator& b, const vector<Pt>::iterator& e) {
    assert(e - b >= 2);
    if (e - b <= 3) {
        long long mind = -1;
        sort(b, e, cmpPtByY);
        for (auto i = b; i < e; i++)
            for (auto j = i + 1; j < e; j++) {
                long long d = dist(*i, *j);
                if (mind < 0 || d < mind) {
                    mind = d;
                }
            }
        return mind;
    }

    auto m = b + (e - b)/2;
    long long d = solve(b, m);
    d = min(d, solve(m, e));

    deque<Pt> S;
    double target_x = m->x;
    double sqrt_d = sqrt(d);

    auto i1 = b;
    auto e1 = m ;
    auto i2 = m;
    auto e2 = e;
    auto i = b;

    long long mind = d;
    while (i1 < e1 || i2 < e2) {
        Pt next;
        if (i1 < e1 && (i2 >= e2 || i1->x <= i2->x)) {
            next = *i1;
            ++i1;
        } else {
            next = *i2;
            ++i2;
        }
        if (target_x - sqrt_d <= next.x + EPS && next.x - EPS <= target_x + d)
            add(S, next, mind);
        *i = next;
        i++;
    }

    return mind;
}

 
int main() {
    int N;

    f >> N;

    vector<Pt> pts(N);
    for (int i = 0; i < N; i++) {
        f >> pts[i].x >> pts[i].y;
    }

    sort(pts.begin(), pts.end(), &cmpPtByX);

    g << fixed << setprecision(7) << sqrt(solve(pts.begin(), pts.end())) << '\n';

 
    f.close();
    g.close();
    return 0;
}