Cod sursa(job #2921957)

Utilizator tzancauraganuTzanca Uraganu tzancauraganu Data 2 septembrie 2022 17:01:31
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.42 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, vector<Pt>& backUp) {
    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;
    double target_x = m->x;
    
    long long d = solve(b, m, backUp);
    d = min(d, solve(m, e, backUp));

    deque<Pt> S;
    double sqrt_d = sqrt(d);

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

    long long mind = d;
    while (i1 < e1 || i2 < e2) {
        Pt next;
        if (i1 < e1 && (i2 >= e2 || i1->y <= i2->y)) {
            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);
        backUp[i++] = next;
    }

    for (auto it = b; it < e; it++)
        *it = backUp[it - b];

    return mind;
}

 
int main() {
    int N;

    f >> N;

    vector<Pt> pts(N), backUp(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(), backUp)) << '\n';

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