Cod sursa(job #2984125)

Utilizator Vlad.Vlad Cristian Vlad. Data 23 februarie 2023 17:03:07
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.1 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define INF 999999999999999999
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");

struct punct {
    long long x, y;
};


unsigned long long dist(punct a, punct b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

bool comp(punct a, punct b) {
    if (a.x == b.x) {
        return a.y < b.y;
    }
    return a.x < b.x;
}

int N;
vector <punct> v, o;

void read() {
    fin >> N;
    punct a;
    for (int i = 0; i < N; ++i) {
        fin >> a.x >> a.y;
        v.push_back(a);
        o.push_back(a);
    }
    sort(v.begin(), v.end(), comp);
    sort(o.begin(), o.end(), comp);
}

vector<punct> interclasare(int left, int mid, int right) {
    vector<punct> so;
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (o[i].y <= o[j].y) {
            so.push_back(o[i]);
            i++;
        }
        else {
            so.push_back(o[j]);
            j++;
        }
    }
    while (i <= mid) {
        so.push_back(o[i]);
        i++;
    }
    while (j <= right) {
        so.push_back(o[j]);
        j++;
    }

    return so;
}

unsigned long long getdist(int left, int right) {

    //special cases

    if (right <= left) {
        return INF;
    }
    if (right - left  == 1) {

        if (o[right].y < o[left].y) {
            swap(o[right], o[left]);
        }

        return dist(v[left], v[right]);
    }

    //general case

    int mid = (right + left) / 2;

    unsigned long long dist1 = getdist(left, mid), dist2 = getdist(mid + 1, right);

    unsigned long long d = min(dist1, dist2);


    vector<punct> so = interclasare(left, mid, right);
    int k = 0;

    for (int i = left; i <= right; ++i) {
        o[i] = so[k];
        ++k;
    }

    int r;

    for (int i = left; i <= right; ++i) {
        r = min(right, i + 7);
        for (int j = i + 1; j <= r; ++j) {
            d = min(d, dist(o[i], o[j]));
        }
    }

    return d;

}

int main()
{
    read();
    fout << setprecision(15) << sqrt(getdist(0, N - 1));
    return 0;
}