Cod sursa(job #1919170)

Utilizator osiaccrCristian Osiac osiaccr Data 9 martie 2017 18:13:29
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

vector <pair<int, int>> c1, c2, c3, c4;

int n, x, y, bi, bj, sol;

int calc (vector <pair<int,int>> a) {
    if (a.size () == 0)
        return 0;
    sort (a.begin (), a.end ());
    int w[500001], k;
    w[1] = a[0].second;
    k = 1;
    for (int i = 1; i <= a.size () - 1; i++) {
        int x = a[i].second;
        int st = 1, dr = k, mid = (st + dr) / 2;
        while (st <= dr) {
            if (w[mid] >= x)
                st = mid + 1;
            else
                dr = mid - 1;
            mid = (st + dr) / 2;
        }
        if (st > k) {
            w[++k] = x;
        }
        else
            w[st] = x;
    }
    return k;
}

int main () {
    fin >> n >> bi >> bj;
    for (int i = 1; i <= n; i++) {
        fin >> x >> y;
        int X = x - bi;
        int Y = y - bj;
        if (X >= 0) {
            if (Y >= 0) {
                c1.push_back (make_pair (X, Y));
            }
            else
                c4.push_back (make_pair (X, Y));
        }
        else {
            if (Y >= 0) {
                c2.push_back (make_pair (X, Y));
            }
            else
                c3.push_back (make_pair (X, Y));
        }
    }

    sol += calc (c1);
    for (int i = 0; i <= c2.size () - 1 && c2.size (); i++) {
        c2[i].first *= -1;
    }
    sol += calc (c2);
    for (int i = 0; i <= c3.size () - 1 && c3.size (); i++) {
        c3[i].first *= -1;
        c3[i].second *= -1;
    }
    sol += calc (c3);
    for (int i = 0; i <= c4.size () - 1 && c4.size (); i++) {
        c4[i].second *= - 1;
    }
    sol += calc (c4);

    fout << sol;

    return 0;
}