Cod sursa(job #3225285)

Utilizator gBneFlavius Andronic gBne Data 17 aprilie 2024 11:40:42
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.94 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

const int NMax = 100000;
pair<int, int> v[NMax + 10];
pair<int, int> tmp[NMax + 10];

int N;

double distanta(int x, int y){
    int x2 = v[y].first, x1 = v[x].first;
    int y2 = v[y].second, y1 = v[x].second;
    return sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1));
}

double solve(int st, int dr){
    if(st == dr){
        return 0;
    }
    else{
        int mij = (st + dr) / 2;
        double s1 = solve(st, mij);
        double s2 = solve(mij + 1, dr);
        if(s1 == 0){
            s1 = distanta(st, st + 1);
        }
        if(s2 == 0){
            s2 = distanta(dr - 1, dr);
        }
        double d = min(s1, s2);
        int k = st, i = st, j = mij + 1;
        while(i <= mij && j <= dr){
            if(v[i].second < v[j].second){
                tmp[k ++] = v[i ++];
            }
            else{
                tmp[k ++] = v[j ++];
            }
        }
        while(i <= mij){
            tmp[k ++] = v[i ++];
        }
        while(j <= dr){
            tmp[k ++] = v[j ++];
        }
        for(int i=st; i<=dr; ++i){
            v[i] = tmp[i];
        }

        i = mij - 1;
        vector<int> v;
        while(distanta(mij, i) <= d && i > 0){
           v.push_back(i);
           -- i;
        }
        i = mij + 1;
        while(distanta(mij, i) <= d && i <= N){
            v.push_back(i);
            ++ i;
        }
        for(int i=0; i<v.size(); ++i){
            for(int j=i+1; j<v.size(); ++j){
                d = min(d, distanta(i, j));
            }
        }
        cout << st << ' ' << dr << ' ' << d << '\n';
        return d;
    }
}

int main()
{
    fin >> N;
    for(int i=1; i<=N; ++i){
        fin >> v[i].first >> v[i].second;
    }
    sort(v + 1, v + N + 1);
    fout << setprecision(10) << solve(1, N) << '\n';
    return 0;
}