Cod sursa(job #2458764)

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

using namespace std;

#define px first
#define py second

const int MAXN = 100005;

pair<int, int> pct[MAXN];
vector<pair<int, int> > Y;

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;
    return min(divide(st, mij), divide(mij + 1, dr));
}

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);
    double mndistrec = divide(1, n);
    int d = (pct[n / 2].px + pct[n / 2 + 1].px) / 2;
    for(int i = 1; i <= n; ++i){
        if(abs(pct[i].px - d) <= mndistrec)
            Y.push_back({pct[i].py, pct[i].px});
    }
    sort(Y.begin(), Y.end());
    double mndistinter = 1e9;
    for(int p = 0; p < (int)Y.size() - 8; ++p){
        double dist1 = calc(Y[p], Y[p + 1]);
        double dist2 = calc(Y[p], Y[p + 2]);
        double dist3 = calc(Y[p], Y[p + 3]);
        double dist4 = calc(Y[p], Y[p + 4]);
        double dist5 = calc(Y[p], Y[p + 5]);
        double dist6 = calc(Y[p], Y[p + 6]);
        double dist7 = calc(Y[p], Y[p + 7]);
        mndistinter = min(mndistinter, min(dist1, min(dist2, min(dist3, min(dist4, min(dist5, min(dist6, dist7)))))));
    }
    fout << fixed << setprecision(7) << min(mndistrec, mndistinter);
    return 0;
}