Cod sursa(job #1133490)

Utilizator iordache.bogdanIordache Ioan-Bogdan iordache.bogdan Data 4 martie 2014 22:27:18
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("pachete.in");
ofstream g("pachete.out");

struct point {
    int x;
    int y;
} v[50005];

const int dx[] = {-1,-1,1,1};
const int dy[] = {-1,1,1,-1};

int n,i,ds,k,st,dr,mid,ok,xp,yp;

int d[50005],x[50005],y[50005];

long long sol;

int modul(int x) {
    return x>0 ? x : -x;
}

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

int rez(void) {
    d[0]=0;
    int i;
    for(i=1;i<=k;i++) {
        st=1;dr=d[0];ok=0;
        while(st<=dr) {
            mid=(st+dr)/2;
            if(d[mid]<=v[i].y) {
                ok=1;
                dr=mid-1;
            }
            else
                st=mid+1;
        }
        if(ok)
            d[st]=v[i].y;
        else
            d[++d[0]]=v[i].y;
    }
    return d[0];
}

int main() {
    f>>n>>xp>>yp;
    for(i=1;i<=n;i++) {
        f>>x[i]>>y[i];
        x[i]-=xp;
        y[i]-=yp;
    }
    for(ds=0;ds<=3;ds++) {
        k=0;
        for(i=1;i<=n;i++)
            if(x[i]*dx[ds]>=0 && y[i]*dy[ds]>=0) {
                v[++k].x=modul(x[i]);
                v[k].y=modul(y[i]);
            }
        sort(v+1,v+k+1,cmp);
        sol+=rez();
    }
    g<<sol<<"\n";
    return 0;
}