Cod sursa(job #3323560)

Utilizator petric_mariaPetric Maria petric_maria Data 18 noiembrie 2025 18:11:42
Problema Tribute Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <bits/stdc++.h>
using namespace std;
ifstream f("tribute.in");
ofstream g("tribute.out");

int n, dx, dy;
int ans_oriz = INT_MAX, ans_vert = INT_MAX;
int a, b, frx[50005], fry[50005], ma_x = INT_MIN, mi_x = INT_MAX, ma_y = INT_MIN, mi_y = INT_MAX;

void orizontala() {
    if (ma_x - mi_x <= dx)
        ans_oriz = 0;
    else {
        int sum_ant = 0, sum_post = 0, points_ant = 0, points_post = 0;

        for (int i=mi_x; i<=ma_x; ++i) {
            if (i > dx) {
                points_post += frx[i];
                sum_post += frx[i] * i;
            }
        }
        ans_oriz = min (ans_oriz, sum_post - points_post * dx);
        for (int i=1; i+dx <= ma_x; ++i) {
            points_ant += frx[i-1];
            sum_ant += frx[i-1] * (i-1);

            points_post -= frx[i+dx];
            sum_post -= frx[i+dx] * (i+dx);

            int dist = points_ant * i - sum_ant + sum_post - points_post * (i+dx);
            ans_oriz = min (ans_oriz, dist);
        }
    }
}


void verticala () {
    if (ma_y - mi_y <= dy)
        ans_vert = 0;
    else {
        int sum_ant = 0, sum_post = 0, points_ant = 0, points_post = 0;

        for (int i=mi_y; i<=ma_y; ++i) {
            if (i > dy) {
                points_post += fry[i];
                sum_post += fry[i] * i;
            }
        }
        ans_vert = min (ans_vert, sum_post - points_post * dy);
        for (int i=1; i+dy <= ma_y; ++i) {
            points_ant += fry[i-1];
            sum_ant += fry[i-1] * (i-1);

            points_post -= fry[i+dy];
            sum_post -= fry[i+dy] * (i+dy);

            int dist = points_ant * i - sum_ant + sum_post - points_post * (i+dy);
            ans_vert = min (ans_vert, dist);
        }
    }
}

int main()
{
    f >> n >> dx >> dy;
    for (int i=1; i<=n; ++i) {
        f >> a >> b;
        frx[a] ++;
        fry[b] ++;
        ma_x = max (ma_x, a);
        mi_x = min (mi_x, a);
        ma_y = max (ma_y, b);
        mi_y = min (mi_y, b);
    }

    orizontala();
    //cout << endl;
    verticala();

    g << ans_oriz + ans_vert;
    return 0;
}