Cod sursa(job #2980028)

Utilizator alexandru_ioan.06Alexandru Ioan alexandru_ioan.06 Data 16 februarie 2023 10:03:14
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.69 kb
#include <bits/stdc++.h>

using namespace std;
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");

const int dim = 1e5 + 5;
const long double INF = 1e9;

struct Vect
{
    int row , col;
};

int n;
Vect v[dim];

bool cmp (Vect a , Vect b)
{
    return a.row < b.row || (a.row == b.row && a.col < b.col);
}

bool cmp1 (Vect a , Vect b)
{
    return a.col < b.col || (a.col == b.col && a.row < b.row);
}

long double Dist(Vect a , Vect b)
{
    long double d1 = a.row - b.row;
    long double d2 = a.col - b.col;
    return sqrt(d1 * d1 + d2 * d2);
}

long double DivideEtImpera(int l , int r)
{
    if(r - l + 1 <= 3)
        {
            long double dist_min = INF;
            for(int i = l ; i <= r ; ++i)
                for(int j = i + 1 ; j <= r ; ++j)
                    dist_min = min(dist_min , Dist(v[j] , v[i]));
            return dist_min;
        }
    else
        {
            int mid = (l + r) / 2;
            long double dist_min = min(DivideEtImpera(l , mid) , DivideEtImpera(mid + 1 , r));
            vector<Vect> p;
            for(int i = l ; i <= r ; ++i)
                if(abs(v[i].row - v[mid].row) <= dist_min)
                    p.push_back(v[i]);
            sort(p.begin() , p.end() , cmp1);
            for(int i = 0 ; i < p.size() ; ++i)
                for(int j = i + 1 ; j < p.size() && j - i + 1 <= 9 ; ++j)
                    dist_min = min(dist_min , Dist(p[i] , p[j]));
            return dist_min;
        }
}

int main()
{
    fin >> n;
    for(int i = 1 ; i <= n ; ++i)
        fin >> v[i].row >> v[i].col;
    sort(v + 1 , v + n + 1 , cmp);
    fout << fixed << setprecision(6) << DivideEtImpera(1 , n);
}