Cod sursa(job #2377969)

Utilizator LolkekzorChiorean Tudor Lolkekzor Data 11 martie 2019 15:26:53
Problema Cele mai apropiate puncte din plan Scor 85
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.9 kb
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <limits>

#include <iostream>
using namespace std;

#define x first
#define y second
#define NMAX 100005

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

int n;
pair<int, int> a;
vector<pair<int, int> > pct;
vector<pair<int, int> > aux(NMAX);

long double dist(int i, int j) {
    return sqrt(1LL * (pct[j].x - pct[i].x) * (pct[j].x - pct[i].x) + 1LL * (pct[j].y - pct[i].y) * (pct[j].y - pct[i].y));
}

void interclass(int l, int mij, int r) {
    int i = l, j = mij + 1, k = 0;
    while (k < r - l + 1) {
        if (i > mij || (j <= r && pct[i].y > pct[j].y)) {
            aux[k++] = pct[j++];
        } else {
            aux[k++] = pct[i++];
        }
    }

    for (i = l, k = 0 ; i <= r ; i++, k++)
        pct[i] = aux[k];
}

long double closestPoints(int l, int r) {
    int mij = (l + r) / 2, i, j;
    long double minDist = std::numeric_limits<double>::max(), minL, minR;
    if (r - l <= 2) {
        for (i = l ; i < r ; i++)
            for (j = i + 1 ; j <= r ; j++)
                minDist = min(minDist, dist(i, j));
        for (i = l ; i < r ; i++)
            for (j = i + 1 ; j <= r ; j++)
                if (pct[i].y > pct[j].y)
                    swap(pct[i], pct[j]);

        return minDist;
    }

    minL = closestPoints(l, mij);
    minR = closestPoints(mij + 1, r);
    interclass(l, mij, r);

    minDist = min(minL, minR);
    for (i = l ; i <= r ; i++) {
        for (j = i + 1 ; j <= min(i + 7, r) ; j++) {
            minDist = min(minDist, dist(i, j));
        }
    }

    return minDist;
}

int main() {
    fin >> n;
    for (int i = 0 ; i < n ; i++) {
        fin >> a.x >> a.y;
        pct.push_back(a);
    }
    sort(pct.begin(), pct.end());

    fout << fixed << setprecision(7) << closestPoints(0, n - 1);
}