Cod sursa(job #3236160)

Utilizator andreea678Rusu Andreea-Cristina andreea678 Data 26 iunie 2024 15:20:48
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#define INF 999999999999999999LL

using namespace std;

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

struct point {
    long long x, y;
};

vector<point> v;

long long distance(point a, point b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

bool compareX(point a, point b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

bool compareY(point a, point b) {
    return a.y < b.y;
}

long long solve(int st, int dr) {
    if (st >= dr) {
        return INF;
    }
    if (dr - st == 1) {
        return distance(v[st], v[dr]);
    }

    int mij = (st + dr) / 2;
    long long d1 = solve(st, mij);
    long long d2 = solve(mij + 1, dr);
    long long dmin = min(d1, d2);

    vector<point> w;
    for (int i = st; i <= dr; ++i) {
        if (abs(v[i].x - v[mij].x) * abs(v[i].x - v[mij].x) <= dmin) {
            w.push_back(v[i]);
        }
    }
    sort(w.begin(), w.end(), compareY);

    for (int i = 0; i < w.size(); ++i) {
        for (int j = i + 1; j < w.size() && (w[j].y - w[i].y) * (w[j].y - w[i].y) <= dmin; ++j) {
            dmin = min(dmin, distance(w[i], w[j]));
        }
    }
    return dmin;
}

int main() {
    fin >> n;
    v.resize(n);
    for (int i = 0; i < n; ++i) {
        fin >> v[i].x >> v[i].y;
    }
    sort(v.begin(), v.end(), compareX);
    long long result = solve(0, n - 1);
    fout << setprecision(6) << fixed << sqrt(result);
    return 0;
}