Cod sursa(job #2488237)

Utilizator danyvsDan Castan danyvs Data 6 noiembrie 2019 15:31:42
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.43 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>

using namespace std;

const int INF = 0x3f3f3f3f;

vector<pair<long long, long long>> points;

void read() {
    ifstream fin("cmap.in");

    long long n;
    fin >> n;
    for (int i = 0; i < n; ++i) {
        long long x, y;
        fin >> x >> y;
        points.emplace_back(make_pair(x, y));
    }

    fin.close();
}

struct cmp {
    bool operator()(const pair<long long, long long> &A, const pair<long long, long long> &B) {
        return A.first < B.first;
    }
};

double dist(const pair<long long, long long> &A, const pair<long long, long long> &B) {
    return sqrt((A.first - B.first) * (A.first - B.first) + (A.second - B.second) * (A.second - B.second));
}

void merge(int left_idx, int mid_idx, int right_idx) {
    int i = left_idx;
    int j = mid_idx;

    vector<pair<long long, long long>> temp;
    while (i < mid_idx && j < right_idx)
        if (points[i].first < points[j].first)
            temp.push_back(points[i++]);
        else
            temp.push_back(points[j++]);

    while (i < mid_idx)
        temp.push_back(points[i++]);

    while (j < right_idx)
        temp.push_back(points[j++]);

    for (int idx = 0; idx < (int)temp.size(); ++idx)
        points[left_idx + idx] = temp[idx];
}

double closest_points(int left_idx, int right_idx) {
    if (left_idx >= right_idx)
        return INF;

    if (left_idx - right_idx == 1) {
        merge(left_idx, left_idx, right_idx);
        return dist(points[left_idx], points[right_idx]);
    }

    int mid_index = left_idx + (right_idx - left_idx) / 2;
    double mid_value = points[mid_index].first;

    double current_best = min(closest_points(left_idx, mid_index), closest_points(mid_index + 1, right_idx));

    merge(left_idx, mid_index, right_idx);

    vector<pair<long long, long long>> temp;
    for (int i = left_idx; i < right_idx; ++i)
        if (abs(points[i].first - mid_value) <= current_best)
            temp.push_back(points[i]);

    for (int i = 0; i < (int)temp.size(); ++i)
        for (int j = i + 1; j < temp.size() && j - i < 8; ++j)
            current_best = min(current_best, dist(temp[i], temp[j]));

    return current_best;
}

void print() {
    ofstream fout("cmap.out");
    fout << fixed << setprecision(6) << closest_points(0, points.size());
    fout.close();
}

int main() {
    read();
    sort(points.begin(), points.end(), cmp());
    print();
    return 0;
}