Cod sursa(job #3281500)

Utilizator vali1234Danciu Valentin-Nicolae vali1234 Data 1 martie 2025 20:51:31
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.5 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <math.h>
#include <float.h>
#include <bits/ranges_algo.h>
#include <iomanip>

std::ifstream fin("cmap.in");
std::ofstream fout("cmap.out");
bool cmpx(std::pair<int, int> a, std::pair<int, int> b) {
    return a.first < b.first;
}

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

double distanta(std::pair<int,int> p1, std::pair<int,int> p2) {
    double tmp1 = (p1.first - p2.first);
    double tmp2 = (p1.second - p2.second);
    return sqrt((double)(tmp1*tmp1 + tmp2*tmp2));
}

double caz_de_baza(std::vector<std::pair<int, int>> v, double d) {
    double mindist = d;
    for (int i=0; i<v.size()-1; i++) {
        for (int j=i+1; j<v.size(); j++) {
            double dist = distanta(v[i], v[j]);
            if (dist < mindist) {
                mindist = dist;
            }
        }
    }
    return mindist;
}
double apropiate_zona(std::vector<std::pair<int, int>> v, double d) {
    double mindist = d;
    std::sort(v.begin(), v.end(), cmpy);
    for (int i=0; i<v.size()-1; i++) {
        for (int j=i+1; j<v.size() and v[j].second - v[i].second < mindist ; j++) {
            if (distanta(v[i],v[j]) < mindist  ) {
                mindist = distanta(v[i], v[j]);
            }
        }
    }
    return mindist;
}
double apropiate(std::vector<std::pair<int, int>> v, int left, int right,double mindist) {
    if (right-left<=3) {
        if (caz_de_baza(v,mindist) < mindist) {
            mindist = caz_de_baza(v,mindist);
            return mindist;
        }

    }
    else {
        int mid = (left+right)/2;
        double d1 = apropiate(v, left, mid,mindist);
        double d2 = apropiate(v, mid+1, right,mindist);
        double currentmind = std::min(d1, d2);

        std::vector<std::pair<int, int>> strip;
        for (int i=left; i<right; i++) {
            if (abs(v[i].first - v[mid].first) < currentmind) {
                strip.push_back(v[i]);
            }
        }
        return std::min(currentmind, apropiate_zona(strip,currentmind));
    }

}



int main(){
   int n;
    std::vector<std::pair<int, int>> v;

    fin>>n;
    for (int i=0;i<n;i++) {
        int x,y;
        fin>>x>>y;
        v.push_back(std::make_pair(x,y));

    }
    std::vector<std::pair<int, int>> vx(v);
    std::vector<std::pair<int, int>> vy(v);
    double d = DBL_MAX;
    sort(vx.begin(), vx.end(), cmpx);
    sort(vy.begin(), vy.end(), cmpy);
    fout<<std::setprecision(6)<<apropiate(v, 0, n,d);
    return 0;
}