Cod sursa(job #1937109)

Utilizator Mircea_DonciuDonciu Mircea Mircea_Donciu Data 23 martie 2017 18:45:01
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include <set>
#include <algorithm>

#define Nmax 50010

#define x first
#define y second

using namespace std;

const int dx[5] = {0 , 1 , 1 , -1 , -1};
const int dy[5] = {0 , 1 , -1 , -1 , 1};

int n , X , Y , i , k , nou_x , nou_y , nr , total;

pair < int , int > a[Nmax] , b[Nmax];

set < int > subsir;

int main()
{
    freopen("pachete.in","r",stdin);
    freopen("pachete.out","w",stdout);

    scanf("%d", &n);

    scanf("%d %d", &X, &Y);

    for (i = 1; i <= n; ++i)
    {
        scanf("%d %d", &a[i].x, &a[i].y);

        a[i].x -= X; a[i].y -= Y;
    }

    for (k = 1; k <= 4; ++k)
    {
        for (nr = 0 , i = 1; i <= n; ++i)
        {
            nou_x = a[i].x * dx[k];
            nou_y = a[i].y * dy[k];

            if (nou_x > 0 && nou_y > 0) b[++nr] = make_pair ( nou_x , nou_y );
        }

        sort(b + 1 , b + nr + 1);

        if (nr) subsir.insert(b[1].y);

        for (i = 2; i <= nr; ++i)
        {
            set < int > :: iterator it = subsir.lower_bound(b[i].y);

            if (it != subsir.begin())
            {
                subsir.erase(--it);
                subsir.insert(b[i].y);
            }
            else if (it == subsir.begin() && *it < b[i].y)
            {
                subsir.erase(--it);
                subsir.insert(b[i].y);
            }
            else subsir.insert(b[i].y);
        }

        total += subsir.size();

        subsir.clear();
    }

    printf("%d\n", total);

    return 0;
}