Cod sursa(job #1912437)

Utilizator mariusn01Marius Nicoli mariusn01 Data 8 martie 2017 08:52:56
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;
int n, sol, i, x, y, X, Y, k;
vector<pair<int, int> > a, b, c, d;
int v[50010];

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

    return k;
}

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

    fin>>n>>x>>y;
    for (i=1;i<=n;i++) {
        fin>>X>>Y;
        X -= x;
        Y -= y;
        if (X > 0) {
            if (Y > 0)
                a.push_back(make_pair(X,Y));
            else
                d.push_back(make_pair(X,Y));
        } else {
            if (Y > 0)
                b.push_back(make_pair(X,Y));
            else
                c.push_back(make_pair(X,Y));

        }
    }

    sol += cadran(a);
    for (i=0;i<b.size();i++)
        b[i].first = -b[i].first;
    sol+=cadran(b);
    for (i=0;i<c.size();i++)
        c[i].first = -c[i].first, c[i].second = -c[i].second;
    sol += cadran(c);
    for (i=0;i<d.size();i++)
        d[i].second = -d[i].second;


    sol += cadran(d);

    fout<<sol;
    return 0;
}