Cod sursa(job #1918160)

Utilizator blackmanta45Andrei blackmanta45 Data 9 martie 2017 14:22:05
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.31 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin ("pachete.in");
ofstream fout ("pachete.out");
int v[50010],i,x,y,n,p,q;

struct coord {
    int x;
    int y;
};
coord a[50010], b[50010], c[50010], d[50010];

int cmp (coord a, coord b){
    if(a.x>b.x)
        return 1;
    else
        if(a.x==b.x && a.y>b.y)
            return 1;
    return 0;
}

int cauta (coord *p){
    int k,mid,st,dr,x;
    if(p[0].x==0)
        return 0;
    sort(p+1,p+p[0].x+1,cmp);
    v[1]=p[1].y;
    k=1;
    for(i=2;i<=p[0].x;i++){
        st=1;
        dr=k;
        x=p[i].y;
        while(st<=dr){
            mid=(st+dr)/2;
            if(v[mid]<=x)
                dr=mid-1;
            else
                st=mid+1;
        }
        if(st>k)
            k++;
        v[st]=x;
    }
    return k;
}

int main () {
    fin>>n;
    fin>>p>>q;
    for(i=1;i<=n;i++){
        fin>>x>>y;
        x-=p;
        y-=q;
        if(x>0)
            if(y>0)
                a[++a[0].x].x=x,a[a[0].x].y=y;
            else
                b[++b[0].x].x=x,b[b[0].x].y=-y;
        else
            if(y>0)
                c[++c[0].x].x=-x,c[c[0].x].y=y;
            else
                d[++d[0].x].x=-x,d[d[0].x].y=-y;
    }
    fout<<cauta(a)+cauta(b)+cauta(c)+cauta(d);
}