Cod sursa(job #3219166)

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


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

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 cmpx(Punct a, Punct b) {
    return a.x < b.x;
}

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

int n;

long long 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;
    long long l = min(divet(st, mij), divet(mij + 1, dr));
    vector < Punct > pct;
    for (int i = st; i <= dr; i++) {
        if ((v[i].x - v[mij].x) * (v[i].x - v[mij].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;
            l = min(l , dist(v[i], v[j]));
        }
    }
    return 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) << sqrt(divet(1, n));
    return 0;
}