Cod sursa(job #2458833)

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

using namespace std;

#define px first
#define py second

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

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){
            double dist = calc(pct[i], pct[i + 1]);
            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(pct[i].py - pct[mij].py) - mindist < -EPS)
            Y.push_back(pct[i]);
    }
    sort(Y.begin(), Y.end());
    for(int i = 0; i < (int)Y.size(); ++i){
        for(int j = i + 1; j < min(i + 10, (int)Y.size()); ++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, comp);
    double mndist = divide(1, n);
    cout  << fixed << setprecision(10) << EPS;
    fout << fixed << setprecision(7) << mndist;
    return 0;
}