Cod sursa(job #2354100)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 24 februarie 2019 21:07:54
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.34 kb
#include <fstream>
#include <cmath>
#include <algorithm>

using namespace std;

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

struct oras
{
    int x, y;
} v[5][50005];

int rezs[50005];

pair <int, int> base;

inline bool cmp(oras a, oras b)
{
    if(a.x == b.x)
        return a.y < b.y;
    return (a.x < b.x);
}

int nrT = 0;

void xSort(int poz)
{
    while(rezs[poz] < rezs[poz - 1] && poz >= 2)
    {
        int aux = rezs[poz];
        rezs[poz] = rezs[poz - 1];
        rezs[poz - 1] = aux;
        --poz;
    }

    while(rezs[poz] > rezs[poz + 1] && poz < nrT)
    {
        int aux = rezs[poz];
        rezs[poz] = rezs[poz + 1];
        rezs[poz + 1] = aux;
        ++poz;
    }
}

void updateRez(int cad, int poz)
{
    int st = 1;
    int dr = nrT;
    int pozX = -1;
    while(st <= dr)
    {
        int mij = (st + dr) / 2;
        if(v[cad][poz].y >= rezs[mij])
        {
            pozX = mij;
            dr = mij - 1;
        }
        else
            st = mij + 1;
    }
    if(pozX == -1)
    {
        rezs[++nrT] = v[cad][poz].y;
        xSort(nrT);
    }
    else
    {
        rezs[pozX] = v[cad][poz].y;
        xSort(pozX);
    }
}

int main()
{
    int n;
    fin >> n;

    fin >> base.first >> base.second;
    for(int i = 1; i <= n; ++i)
    {
        int pozX, pozY;
        fin >> pozX >> pozY;

        pozX -= base.first;
        pozY -= base.second;

        if(pozX >= 0 && pozY >= 0)
            ++v[1][0].x, v[1][v[1][0].x].x = pozX, v[1][v[1][0].x].y = pozY;
        else if(pozX < 0 && pozY >= 0)
            ++v[2][0].x, v[2][v[2][0].x].x = -pozX, v[2][v[2][0].x].y = pozY;
        else if(pozX < 0 && pozY < 0)
            ++v[3][0].x, v[3][v[3][0].x].x = -pozX, v[3][v[3][0].x].y = -pozY;
        else if(pozX >= 0 && pozY < 0)
            ++v[4][0].x, v[4][v[4][0].x].x = pozX, v[4][v[4][0].x].y = -pozY;
    }


    int sol = 0;
    for(int cd = 1; cd <= 4; ++cd)
    {
        int i = 1;
        int lg = v[cd][0].x;
        sort(v[cd] + 1, v[cd] + lg + 1, cmp);
        while(i <= v[cd][0].x)
        {
            updateRez(cd, i);
            ++i;
        }
        for(int i = 1; i <= nrT; ++i)
            rezs[i] = 0;
        sol += nrT;
        nrT = 0;
    }

    fout << sol << '\n';
    return 0;
}