Cod sursa(job #3244003)

Utilizator MikeStrikeAgache Mihai MikeStrike Data 22 septembrie 2024 20:55:23
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.51 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;


const int MAX_N = 100005;
const long long INF = 4e18;

vector<pair<long long, long long>> V(MAX_N), X, Y;

long long dist(const pair<long long, long long>& a, const pair<long long, long long>& b) {
    return (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

void interclasare(vector<pair<long long, long long>>& arr, int leftStart, int leftEnd, int rightStart, int rightEnd, vector<pair<long long, long long>>& result) {
    int i = leftStart, j = rightStart;
    int idx = 0;


    while (i < leftEnd && j < rightEnd) {
        if (arr[i] <= arr[j]) {
            result[idx++] = arr[i++];
        } else {
            result[idx++] = arr[j++];
        }
    }


    while (i < leftEnd) {
        result[idx++] = arr[i++];
    }


    while (j < rightEnd) {
        result[idx++] = arr[j++];
    }
}

void copiere(vector<pair<long long, long long>>& src, int start, int end, vector<pair<long long, long long>>& dest, int destStart) {
    for (int i = start; i < end; ++i) {
        dest[destStart++] = src[i];
    }
}

long long solve(int st, int dr, vector<pair<long long, long long>>& X, vector<pair<long long, long long>>& Y) {
    if (st >= dr - 1)
        return INF;
    else if (dr - st == 2) {
        if (Y[st] > Y[st + 1])
            swap(Y[st], Y[st + 1]);
        return dist(X[st], X[st + 1]);
    }

    int mid = (st + dr) / 2;
    long long best = min(solve(st, mid, X, Y), solve(mid, dr, X, Y));


    interclasare(Y, st, mid, mid, dr, V);
    copiere(V, 0, dr - st, Y, st);

    int v_size = 0;
    for (int i = st; i < dr; ++i) {
        if (abs(Y[i].second - X[mid].first) <= best) {
            V[v_size++] = Y[i];
        }
    }

    for (int i = 0; i < v_size - 1; ++i) {
        for (int j = i + 1; j < v_size && j - i < 8; ++j)
            best = min(best, dist(V[i], V[j]));
    }

    return best;
}

int main() {
    int n;
    ifstream fin("cmap.in");
    ifstream fout("cmap.out");
    fin >> n;

    X.resize(n), Y.resize(n);
    for (int i = 0; i < (int) X.size(); ++i) {
        fin >> X[i].first >> X[i].second;
    }

    sort(X.begin(), X.end());
    for (int i = 0; i < (int) X.size(); ++i)
        Y[i] = make_pair(X[i].second, X[i].first);

  
    fout << fixed << setprecision(6) << sqrt(solve(0, (int)X.size(), X, Y)) << "\n";

    return 0;
}