Cod sursa(job #2490547)

Utilizator dragos99Homner Dragos dragos99 Data 10 noiembrie 2019 14:51:28
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include<bits/stdc++.h>
#define ll long long

using namespace std;

    ifstream f("cmap.in");
    ofstream g("cmap.out");

vector< pair<ll, ll> > x, y;
vector< pair<ll, ll> > v(100002);

ll getDist(pair<ll, ll> &a, pair<ll, ll> &b)
{
    return  (a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second);
}

ll solve(int st, int dr)
{
    if(dr - st <= 1){
        return 2e18;
    }
    if(dr - st == 2){
        if (y[st] > y[st + 1])
            swap(y[st], y[st + 1]);
        return getDist(x[st], x[st + 1]);
    }
    ll mid = (st + dr) / 2;
    ll result = min(solve(st, mid), solve(mid, dr));

    sort(y.begin() + st, y.begin() + dr);

    ll k = 0;
    for (int i = st; i < dr; i++)
        if (abs(y[i].second - x[mid].first) <= result)
            v[k++] = y[i];
    for (int i = 0; i < k - 1; i++) {
        for (int j = i + 1; j < k && j - i < 8; j++)
            result = min(result, getDist(v[i], v[j]));
    }
    return result;
}

int main()
{
    int n;
    f>>n;
    x.resize(n); y.resize(n);
    for(int i = 0 ; i < n ; i++){
        f>>x[i].first>>x[i].second;
    }

    sort(x.begin(), x.end());

    for(int i = 0 ; i < n ; i++){
        y[i].second = x[i].first;
        y[i].first = x[i].second;
    }

    int sol = solve(0, n);
    g<<fixed<<setprecision(6)<<sqrt(sol);

    return 0;
}