Cod sursa(job #2266089)

Utilizator eu3neuomManghiuc Teodor-Florin eu3neuom Data 22 octombrie 2018 11:03:55
Problema Cele mai apropiate puncte din plan Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

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

const ld INF = 1e13;

vector < pair < ld, ld > > points;
vector < pair < ld, ld > > strip;

ld getDistance(const pair < ld, ld > &a, const pair < ld, ld > &b) {
    return sqrtl((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
ld Solve(int s, int e) {
    if(s + 1 >= e) return INF;
    int mid = (s + e) / 2;
    ld dist = min(Solve(s, mid), Solve(mid, e));

    int idx = 0;
    for(int i = s; i < e; ++i) {
        if(abs(points[mid].first - points[i].first) < dist) {
            strip[idx++] = points[i];
        }
    }

    sort(strip.begin(), strip.begin() + idx, [&](const pair < ld, ld > &a, const pair < ld, ld > &b) {
        return a.second < b.second;
    });

    for(int i = 0; i < idx; ++i) {
        for(int j = i + 1; j < min(i + 8, idx); ++j) {
            dist = min(dist, getDistance(strip[i], strip[j]));
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    fin.tie(0); fout.tie(0);

    int n; fin >> n;
    points.resize(n); strip.resize(n);
    for(int i = 0; i < n; ++i) {
        fin >> points[i].first >> points[i].second;
    }

    sort(points.begin(), points.end());
    fout << fixed << setprecision(10) << Solve(0, n);
    return 0;
}