Cod sursa(job #3292292)

Utilizator MAT696912Tudor Andrei MAT696912 Data 7 aprilie 2025 20:06:58
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.02 kb
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <fstream>
using namespace std;

ifstream fin("cmap.in");

double dist(pair<int, int> a, pair<int, int> b)
{
    return sqrt(pow(a.first - b.first, 2) + pow(a.second - b.second, 2));
}


bool compX(pair<int, int> a, pair<int, int> b)
{
    return a.first < b.first;
}

bool compY(pair<int, int> a, pair<int, int> b)
{
    return a.second < b.second;
}

double median(vector<pair<int, int>> &points, int start, int end)
{
    int mid = (start + end) / 2;
    double l = (double)(points[mid].first + points[mid + 1].first) / 2.0;
    return l;
}

double min_dist(vector<pair<int, int>> &points, int start, int end)
{

    if (end - start == 1) {
        return DBL_MAX;
    }

    if (end - start == 2) {
        return dist(points[start], points[end - 1]);
    }
    int mid = (start + end) / 2;
    double d1 = min_dist(points, start, mid);
    double d2 = min_dist(points, mid, end);

    double minimum = min(d1, d2);
    vector<pair<int, int>> closer_to_median;

    double mid_ = median(points, start, end);

    for (int i = start; i < end; i++) {
        if (points[i].first - mid_ < minimum) {
            closer_to_median.push_back(points[i]);
        }
    }
    
    sort(closer_to_median.begin(), closer_to_median.end(), compY);
    for (int i = 0; i < closer_to_median.size(); i++) {
        for (int j = 1; j < 6 && i + j < closer_to_median.size(); j++) {
            if (dist(closer_to_median[i], closer_to_median[i + j]) < minimum) {
                minimum = dist(closer_to_median[i], closer_to_median[i + j]);
            }
        }
    }

    return minimum;
    

}



int main()
{   
    int n;
    fin >> n;
    vector<pair<int, int>> points(n);
    for (int i = 0; i < n; i++) {
        fin >> points[i].first >> points[i].second;
    }
    FILE* f = fopen("cmap.out", "w");
    sort(points.begin(), points.end(), compX);

    fprintf(f, "%.6f", min_dist(points, 0, n));
}