Cod sursa(job #2293154)

Utilizator MaxTeoTeo Oprescu MaxTeo Data 30 noiembrie 2018 16:45:37
Problema Pachete Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.56 kb
#include <bits/stdc++.h>
using namespace std;

ifstream f("pachete.in");
ofstream g("pachete.out");

const int NMAX = 5e4 + 5;

struct point
{
    int x, y;
};
point cadran[4][NMAX];
point pct;
//point v[NMAX];

int n;
int s[NMAX], t[4];

void Read()
{
    int X, Y;

    f >> n;
    f >> pct.x >> pct.y;
    for(int i = 1; i <= n; ++i)
    {
        f >> X >> Y;
        X -= pct.x;
        Y -= pct.y;

        if( X >= 0 && Y >= 0)   /// cadranul I
            cadran[0][++t[0]] = {X, Y};
        else
        if( X >= 0 && Y < 0)    /// cadranul II
            cadran[1][++t[1]] = {X, -Y};
        else
        if( X < 0 && Y < 0)     /// cadranul III
            cadran[2][++t[2]] = {-X, -Y};
        else
        if( X < 0 && Y >= 0)    /// cadranul IV
            cadran[3][++t[3]] = {-X, Y};
    }
}

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

int Solve(point p[], int n)
{
    int m = 0, j, pas = 1 << 16;

    sort(p + 1, p + n + 1, cmp);
    for(int i = 1; i <= n; ++i)
    {
        j = 0;
        for(int pas = 1 << 15; pas; pas >>= 1)
            if(j + pas <= m && s[j + pas] <= p[i].y)
                j += pas;
        ++j;
        if(j > m)
            s[++m] = p[i].y;
        else
            s[j] = p[i].y;
    }

    return m;

}

void Print()
{
    g << Solve(cadran[0], t[0]) + Solve(cadran[1], t[1]) + Solve(cadran[2], t[2]) + Solve(cadran[3], t[3]);
    g << "\n";
}

int main()
{
    Read();
    Print();
    return 0;
}