Cod sursa(job #2458844)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 21 septembrie 2019 17:03:42
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <bits/stdc++.h>

using namespace std;

#define px first
#define py second

const int MAXN = 100005;

pair<int, int> pct[MAXN];

bool comp(pair<int, int> a, pair<int, int> b){
    return a.py < b.py;
}

long long calc(pair<int, int> a, pair<int, int> b){
    return 1LL * (a.px - b.px) * (a.px - b.px) + 1LL * (a.py - b.py) * (a.py - b.py);
}

long long divide(int st, int dr){
    if(dr - st + 1 <= 3){
        long long ret = 1LL << 60;
        for(int i = st; i <= dr; ++i){
            for(int j = i + 1; j <= dr; ++j)
                ret = min(ret, calc(pct[i], pct[j]));
        }
        return ret;
    }
    int mij = (st + dr) / 2;
    long long mindist = min(divide(st, mij), divide(mij + 1, dr));
    vector<pair<int, int> > Y;
    for(int i = st; i <= dr; ++i){
        if(abs(pct[i].px - pct[mij].px) < mindist)
            Y.push_back(pct[i]);
    }
    sort(Y.begin(), Y.end(), comp);
    for(int i = 0; i < (int)Y.size(); ++i){
        for(int j = i + 1; j < (int)Y.size() && j - i < 8; ++j)
            mindist = min(mindist, calc(Y[i], Y[j]));
    }
    return mindist;
}

int main()
{
    ifstream fin("cmap.in");
    ofstream fout("cmap.out");
    int n;
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> pct[i].px >> pct[i].py;
    sort(pct + 1, pct + n + 1);
    fout << fixed << setprecision(6) << sqrt((long double)divide(1, n));
    return 0;
}