Cod sursa(job #1937119)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 23 martie 2017 18:52:14
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <algorithm>
#include <vector>
#define DIM 50001
using namespace std;
int n,i,x,y,X,Y,k,sol;
//pair <int,int> a[DIM],b[DIM],c[DIM],d[DIM];
vector < pair<int,int> > a,b,c,d;
int v[DIM];
ifstream fin ("pachete.in");
ofstream fout ("pachete.out");
int functie (vector< pair<int,int> > A ){
    if (A.size() == 0)
        return 0;
    sort (A.begin(),A.end());
    k = 1;
    v[k] = A[0].second;
    int dim = A.size();
    for (int i = 1;i<dim;i++){
        int st = 1;
        int dr = k;
        while (st <= dr){
            int mid = (st+dr)/2;
            if (v[mid] > A[i].second)
                st = mid+1;
            else
                dr = mid-1;
        }
        if (st > k)
            k++;
        v[st] = A[i].second;
    }
    return k;
}
int main (){

    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 += functie (a);
    for (i=0;i<b.size();i++)
        b[i].first = -b[i].first;
    sol += functie (b);
    for (i=0;i<c.size();i++)
        c[i].first = -c[i].first, c[i].second = -c[i].second;
    sol += functie (c);
    for (i=0;i<d.size();i++)
        d[i].second = -d[i].second;
    sol += functie (d);
    fout<<sol;


    return 0;
}