Cod sursa(job #3223038)

Utilizator unomMirel Costel unom Data 12 aprilie 2024 10:54:05
Problema Cele mai apropiate puncte din plan Scor 75
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <fstream>
#include <iomanip>
#include <cmath>
#include <algorithm>

using namespace std;

#define int long long

ifstream in("cmap.in");
ofstream out("cmap.out");
int n;
pair<int, int> v[100005];
pair<int, int> w[100005];
int INF = 4e18;

int dist(pair<int, int> a, pair<int, int> b)
{
    return ((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    if(a.second == b.second)
    {
        return a.first < b.first;
    }

    return a.second < b.second;
}

int solve(int st, int dr)
{
    if(st == dr)
    {
        return INF;
    }

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

    int cnt = 0;
    int distanta;
    for(int i = st; i<=dr; i++)
    {
        distanta = abs(v[i].first - v[mij].first) * abs(v[i].first - v[mij].first);
        if(distanta <= dmin)
        {
            cnt++;
            w[cnt] = v[i];
        }
    }

    //sort(w+1, w+cnt+1, cmp);

    for(int i = 1; i<=cnt; i++)
    {
        for(int j = i + 1; j<=cnt; j++)
        {
            dmin = min(dmin, dist(w[i], w[j]));
        }
    }


    return dmin;
}

signed main()
{
    in>>n;

    for(int i = 1; i<=n; i++)
    {
        in>>v[i].first>>v[i].second;
    }

    sort(v+1, v+n+1);

    out<<setprecision(6)<<fixed<<sqrt(solve(1, n));

    return 0;
}