Cod sursa(job #2458835)

Utilizator andreisontea01Andrei Sontea andreisontea01 Data 21 septembrie 2019 16:49:34
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>

using namespace std;

#define px first
#define py second

const int MAXN = 100005;
double EPS = 1e-7;

pair<int, int> pct[MAXN];

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

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

double divide(int st, int dr){
    if(dr - st + 1 <= 3){
        double ret = 1e9;
        for(int i = st; i <= dr; ++i){
            for(int j = i + 1; j <= dr; ++j){
                double dist = calc(pct[i], pct[j]);
                ret = min(ret, dist);
            }
        }
        return ret;
    }
    int mij = (st + dr) / 2;
    double mindist = min(divide(st, mij), divide(mij + 1, dr));
    vector<pair<int, int> > Y;
    for(int i = st; i <= dr; ++i){
        if(abs(abs(pct[i].py - pct[mij].py) - mindist) < EPS)
            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(7) << divide(1, n);
    return 0;
}