Cod sursa(job #1524248)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 13 noiembrie 2015 18:45:37
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

struct point {
    int x, y;

    point (int _x = 0, int _y = 0): x(_x), y(_y) {
        if (x < 0)
            x = -x;
        if (y < 0)
            y = -y;
    }
};

bool operator< (const point &a, const point &b) {
    return a.x < b.x;
}

vector <point> points[4];

inline int solve (vector <point> points) {
    sort(points.begin(), points.end());

    vector <int> ys;

    int st, dr, mijl, rasp;
    for (int i = 0; i < points.size(); ++ i) {
        st = 0;
        dr = ys.size() - 1;

        rasp = ys.size();

        while (st <= dr) {
            mijl = (st + dr) >> 1;

            if (ys[mijl] < points[i].y) {
                rasp = mijl;
                dr = mijl - 1;
            }
            else
                st = mijl + 1;
        }

        if (rasp == ys.size())
            ys.push_back(points[i].y);
        else
            ys[rasp] = points[i].y;
    }

    return ys.size();
}

int main()
{
    ifstream cin("pachete.in");
    ofstream cout("pachete.out");

    int n = 0;
    int ox = 0, oy = 0;

    cin >> n >> ox >> oy;

    int x, y;
    for (int i = 1; i <= n; ++ i) {
        cin >> x >> y;

        x -= ox;
        y -= oy;

        if (x > 0) {
            if (y > 0)
                points[0].push_back(point(x, y));
            else
                points[3].push_back(point(x, y));
        }
        else {
            if (y > 0)
                points[1].push_back(point(x, y));
            else
                points[2].push_back(point(x, y));
        }
    }

    int ans = 0;
    for (int i = 0; i < 4; ++ i)
        ans += solve(points[i]);

    cout << ans << '\n';

    cin.close();
    cout.close();
    return 0;
}