Cod sursa(job #2960410)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 4 ianuarie 2023 12:39:54
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <cmath>

using namespace std;
ifstream cin ("cmap.in");
ofstream cout ("cmap.out");

vector<pair<long double , long double>> v;

bool cmp (pair<long double , long double> a , pair<long double , long double> b)
{
    return a.first < b.first || (a.first == b.first && a.second < b.second);
}

bool cmp1(pair<long double , long double> a , pair<long double , long double> b)
{
    return a.second < b.second || (a.second == b.second && a.first < b.first);
}

long double Distanta(pair<long double , long double> a , pair<long double , long double> b)
{
    long double d1 = a.first - b.first;
    long double d2 = a.second - b.second;
    return sqrt(d1 * d1 + d2 * d2);
}

double MinDist(int l , int r)
{
    if(r - l + 1 <= 3)
        {
            long double dist_min = 2e9;
            for(int i = l ; i <= r ; ++i)
                for(int j = i+1 ; j <= r ; ++j)
                    dist_min = min(dist_min , Distanta(v[i] , v[j]));
            return dist_min;
        }
    else
        {
            int mid = (l+r) / 2;
            long double dist_min = min(MinDist(l , mid) , MinDist(mid+1 , r));
            vector<pair<long double , long double>> puncte;
            for(int i = l ; i <= r ; ++i)
                if(abs(v[i].first - v[mid].first <= dist_min))
                    puncte.push_back(v[i]);
            sort(puncte.begin() , puncte.end() , cmp1);
            for(int i = 0 ; i < puncte.size() ; ++i)
                for(int j = i+1 ; j < puncte.size() && j <= i+8 ; ++j)
                    dist_min = min(dist_min , Distanta(puncte[i] , puncte[j]));
            return dist_min;
        }
}

int main()
{
    int n;
    cin >> n;
    for(int i = 1 ; i <= n ; ++i)
        {
            int x , y;
            cin >> x >> y;
            v.push_back({x , y});
        }
    sort(v.begin() , v.end() , cmp);
    cout << fixed << setprecision(6) << MinDist(0 , n-1);
}