Cod sursa(job #2270690)

Utilizator LeVladzCiuperceanu Vlad LeVladz Data 27 octombrie 2018 13:38:33
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <fstream>
#include <algorithm>
#define x first
#define y second

using namespace std;

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

int n,xx,yy,i,k[5],t,u[50005];
pair<int, int> v[50005],cad[5][50005];

int main()
{
    fin >> n;
    fin >> xx >> yy;
    for (i=1; i<=n; i++)
    {
        fin >> v[i].x >> v[i].y;
        v[i].x -= xx;
        v[i].y -= yy;
    }
    for (i=1; i<=n; i++)
    {
        if (v[i].x >= 0 && v[i].y >= 0)
           cad[1][++k[1]] = v[i];
        if (v[i].x < 0 && v[i].y >= 0)
        {
            v[i].x = v[i].x*(-1);
            cad[2][++k[2]] = v[i];
        }
        if (v[i].x < 0 && v[i].y < 0)
        {
            v[i].x = v[i].x*(-1);
            v[i].y = v[i].y*(-1);
            cad[3][++k[3]] = v[i];
        }
        if (v[i].x >= 0 && v[i].y < 0)
        {
            v[i].y = v[i].y*(-1);
            cad[4][++k[4]] = v[i];
        }
    }
    int nrdrum = 0;
    for (int cadr=1; cadr<=4; cadr++)
    {
        if (k[cadr] == 0)
            continue;
        sort(cad[cadr]+1, cad[cadr]+k[cadr]+1);
        u[1] = cad[cadr][1].y;
        int t = 1;
        for (i=2; i<=k[cadr]; i++)
        {
            int st = 1;
            int dr = t;
            int maxim = 0;
            int ok = 0; int poz = 0;
            while (st <= dr)
            {
                int mid = (st+dr)/2;
                if (cad[cadr][i].y >= u[mid])
                {
                    if (u[mid] >= maxim)
                    {
                        maxim = u[mid];
                        poz = mid;
                        ok = 1;
                    }
                    dr = mid-1;
                }
                else
                    st = mid+1;
            }
            if (ok == 0)
                u[++t] = cad[cadr][i].y;
            else
                u[poz] = cad[cadr][i].y;
        }
        nrdrum += t;
    }
    fout << nrdrum;
    return 0;
}