Cod sursa(job #1991843)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 18 iunie 2017 14:59:12
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("pachete.in");
ofstream out("pachete.out");
int n,xi,xj,x,y,an,bn,cn,dn,av,bv,cv,dv,ao,bo,co,dot,i,w[50000],sol;
pair<int,int>a[50001],b[50001],c[50001],d[50001],v[50001];
int solve( int n ){
    int i,k = 0,st,dr,mid;
    sort( v + 1, v + n + 1 );
    for( i = 1; i <= n; i ++ ){
        if( v[i].second > w[k] ){
            k ++;
            w[k] = v[i].second;
        }
        else{
            for( st = 1, dr = k; st <= dr; ){
                mid = (st + dr)/2;
                if( w[mid] < v[i].second ){
                    st = mid + 1;
                }
                else{
                    dr = mid - 1;
                }
            }
            w[st] = v[i].second;
        }
    }
    return k;
}
int main(){
    in >> n;
    in >> xi >> xj;
    for( i = 1; i <= n; i ++ ){
         in >> x >> y;
         if( x >= xi && y > xj ){
            a[++an].first = x-xi;
            a[an].second = y-xj;
         }
         if( x < xi && y >= xj ){
            b[++bn].first = x-xi;
            b[bn].second = y-xj;
         }
         if( x > xi && y <= xj ){
            c[++cn].first = x-xi;
            c[cn].second = y-xj;
         }
         if( x <= xi && y < xj ){
            d[++dn].first = x - xi;
            d[dn].second = y - xj;
         }
    }
    for( i = 1; i <= an; i ++ ){
        v[i].first = a[i].first;
        v[i].second = a[i].second;
    }
    sol += solve( an );
    for( i = 1; i <= bn; i ++ ){
        v[i].first = b[i].first*-1;
        v[i].second = b[i].second;
    }
    sol += solve( bn );
    for( i = 1; i <= cn; i ++ ){
        v[i].first = c[i].first;
        v[i].second = c[i].second*-1;
    }
    sol += solve( cn );
    for( i = 1; i <= dn; i ++ ){
        v[i].first = d[i].first*-1;
        v[i].second = d[i].second*-1;
    }
    sol += solve( dn );
    out << sol;
}