Cod sursa(job #3219158)

Utilizator Xutzu358Ignat Alex Xutzu358 Data 30 martie 2024 11:52:16
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");


struct Punct {
    int x, y;
}v[100005];

double dist(Punct a, Punct b) {
    return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

bool cmpx(Punct a, Punct b) {
    return a.x < b.x;
}

bool cmpy(Punct a, Punct b) {
    return a.y < b.y;
}

int n;

double divet(int st, int dr) {
    if (st + 1 == dr) {
        return dist(v[st], v[dr]);
    }
    else if (st + 2 == dr) {
        return min(min(dist(v[st], v[st + 1]), dist(v[st + 1], v[st + 2])), dist(v[st], v[st + 2]));
    }
    int mij = (st + dr) / 2;
    double l = min(divet(st, mij), divet(mij + 1, dr));
    double d = 1000000000000000000;
    int x = v[mij].x;
    vector < Punct > pct;
    for (int i = st; i <= dr; i++) {
        if (abs(v[i].x - x) <= l) pct.push_back(v[i]);
    }
    sort(pct.begin(), pct.end(), cmpy);
    for (int i = 0; i < pct.size(); i++) {
        for (int j = i + 1; j < pct.size(); j++) {
            //if (abs(v[i].y - v[j].y) > l) break;
            d = min(d, dist(v[i], v[j]));
        }
    }
    return min(d, l);
}

int main()
{
    f >> n;
    for (int i = 1; i <= n; i++) {
        f >> v[i].x >> v[i].y;
    }
    sort(v + 1, v + n + 1, cmpx);
    g << fixed << setprecision(6) << divet(1, n);
    return 0;
}