Cod sursa(job #2163490)

Utilizator TudoseSanzianaTudose Sanziana TudoseSanziana Data 12 martie 2018 18:30:38
Problema Tribute Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.03 kb
#include <bits/stdc++.h>
using namespace std;

ifstream in("tribute.in");
ofstream out("tribute.out");

const int COORD_MAX = 50000;

int n, dx, dy, x, y;

int ansX, ansY;
int stX[COORD_MAX + 2], drX[COORD_MAX + 2];
int stY[COORD_MAX + 2], drY[COORD_MAX + 2];

void calcSt()
{
    for(int i = 1; i <= COORD_MAX; i++)
    {
        stX[i] += stX[i - 1];
        stY[i] += stY[i - 1];
    }
}

void calcDr()
{
    for(int i = COORD_MAX - 1; i >= 0; i--)
    {
        drX[i] += drX[i + 1];
        drY[i] += drY[i + 1];
    }
}

int main()
{
    in >> n >> dx >> dy;
    while(n--)
    {
        in >> x >> y;
        stX[x + 1]++; drX[x - 1]++;
        stY[y + 1]++; drY[y - 1]++;
    }

    calcSt();
    calcSt();
    calcDr();
    calcDr();

    ansX = ansY = COORD_MAX + 10;
    for(x = 0; x <= COORD_MAX; x++)
        ansX = min(ansX, stX[x] + drX[x + dx]);

    for(y = 0; y <= COORD_MAX; y++)
        ansY = min(ansY, stY[y] + drY[y + dy]);

    out << ansX + ansY << '\n';

    return 0;
}