Cod sursa(job #1591057)

Utilizator BugirosRobert Bugiros Data 5 februarie 2016 18:58:27
Problema Tribute Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <fstream>
#include <algorithm>
using namespace std;

const int MAXN = 50005;
const int INF = 1 << 30;

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

int n,dx,dy;
int x[MAXN],y[MAXN];
int rasp_1,rasp_2;


void citire()
{
    in >> n >> dx >> dy;
    for (int i = 1;i <= n;++i)
        in >> x[i] >> y[i];
}


void calculare(int v[],int &rasp,int dim)
{
    sort(v + 1, v + n + 1);
    v[n + 1] = INF;
    v[0] = -INF;
    int poz = 1;
    int dst[MAXN] = {0}, ddr[MAXN] = {0};
    int cati = 0;
    for (int i = v[0];i < MAXN && poz <= n;++i)//parcurgere stanga
    {
        while(poz <= n && v[poz] < i)
        {
            ++cati;
            ++poz;
        }
        dst[i] = dst[i - 1] + cati;
    }

    poz = n;
    cati = 0;
    for (int i = v[n];i >= 0 && poz > 0;--i)//parcurgere dreapta
    {
        while(v[poz] > i)
        {
            ++cati;
            --poz;
        }
        ddr[i] = ddr[i + 1] + cati;
    }

    rasp = INF;

    for (int i = 0;i + dim <= v[n];++i)
    {
        int nr = dst[i] + ddr[i + dim];
        if (nr < rasp)
            rasp = nr;
    }

}

int main()
{
    citire();
    calculare(x,rasp_1,dx);
    calculare(y,rasp_2,dy);
    out << rasp_1 + rasp_2 << '\n';
    return 0;
}