Cod sursa(job #3277282)

Utilizator marelucaMare Luca Ghita mareluca Data 15 februarie 2025 16:38:53
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>

std::ifstream fin("tribute.in");
std::ofstream fout("tribute.out");

std::vector<int> X, Y;

int calculare_distanta(std::vector<int> a, int d) {
    std::sort(a.begin(), a.end());

    int st = 0, dr = a.size() - 1, distantaMinima = 0;
    while (a[dr] - a[st] - d > 0) {
        // Adaugam la distanta a[dr], dx si scadem a[st]
        distantaMinima = distantaMinima + a[dr] - a[st] - d;

        // Practic, incepem in punctul cel mai mic / apropiat
        // Ne apropiem de puncele din dreapta (cele mai mari / indepartate)
        // cat timp distanta ramane pozitiva
        // adica ne apropiem de mai multe puncte in dreapta
        // decat ne indepartam in stanga

        st++; // Ne mutam mai la stanga
        dr--; // Luam celelalte puncte indepartate
    }

    // Astfel, vom obtine o distanta minima
    return distantaMinima;
}

int main() {
    int n, dx, dy;

    fin >> n >> dx >> dy;
    while (n--) {
        int x, y;
        fin >> x >> y;
        X.push_back(x), Y.push_back(y);
    }

    // Vom folosi un algoritm separat, pentru abscisa si ordonata
    fout << calculare_distanta(X, dx) + calculare_distanta(Y, dy);
    return 0;
}