Cod sursa(job #2486361)

Utilizator mirunazMiruna Zavelca mirunaz Data 2 noiembrie 2019 19:08:35
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.54 kb
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
using namespace std;
#define x first
#define y second
ifstream in("cmap.in");
ofstream out("cmap.out");

double dist_calc(int x1, int x2, int y1, int y2) {
    double d = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    return sqrt(d);
}

double div_et_imp(pair<int, int> v[], int n) {
    double dist_min = dist_calc(v[0].x, v[1].x, v[0].y, v[1].y);
    for (int i = 0; i < n; i ++) {
        for (int j = i + 1; j < n; j ++) {
            double dist = dist_calc(v[i].x, v[j].x, v[i].y, v[j].y);
            if (dist < dist_min)    dist_min = dist;
        }
    }
    return dist_min;
}

int main() {
    int n;
    in >> n;
    pair<int, int> p[n + 1];
    double x_med = 0;
    for (int i = 0; i < n; i ++) {
        in >> p[i].x >> p[i].y;
        x_med += p[i].x;
    }
    x_med /= n;
    pair<int, int> a[n / 2 + 1], b[n / 2 + 1];
    int pa = 0, pb = 0;
    for (int i = 0; i < n; i ++) {
        if (p[i].x < x_med) a[pa ++] = p[i];
        else if (p[i].x > x_med) b[pb ++] = p[i];
    }
    double d = min(div_et_imp(a, pa), div_et_imp(b, pb));
    vector <pair<int, int>> v;
    for (int i = 0; i < n; i ++) {
        if (abs(x_med - p[i].x) <= d)   v.push_back({p[i].y, p[i].x});
    }
    sort(v.begin(), v.end());
    for (int i = 0; i < v.size(); i ++) {
        for (int j = i + 1; j < i + 8 && j < v.size(); j ++) {
            d = min(d, dist_calc(v[i].y, v[j].y, v[i].x, v[j].x));
        }
    }
    out << fixed << setprecision(6) << d;
    return 0;
}