Cod sursa(job #1304269)

Utilizator ovidiuz98Zamfir Ovidiu ovidiuz98 Data 28 decembrie 2014 20:01:13
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.14 kb
#include <fstream>
#include <algorithm>
#define x first
#define y second
using namespace std;

ifstream fin("pachete.in");
ofstream fout("pachete.out");
pair <int,int> v[50002],c[50002];
int a,b,n,d[50002],q,s,p,mid,k,nr,i,u;
int di[]={1,1,-1,-1},dj[]={1,-1,1,-1};
int main(){
    fin>>n>>a>>b;
    for(i=1;i<=n;i++){
        fin>>v[i].x>>v[i].y;
        v[i].x-=a;
        v[i].y-=b;
    }
    for(k=0;k<4;k++){
        nr=0;
        for(i=1;i<=n;i++){
            if(v[i].x*di[k]>=0 && v[i].y*dj[k]>=0){
                c[++nr].x=v[i].x*di[k];
                c[nr].y=v[i].y*dj[k];
            }
        }
        q=0;
        sort(c+1,c+nr+1);
        if(nr!=0){
            d[0]=-1;
            d[++q]=1;
        }
        for(i=2;i<=nr;i++){
            p=1;
            u=q;
            while(p<=u){
                mid=(p+u)/2;
                if(c[d[mid]].y>c[i].y)
                    p=mid+1;
                else
                    u=mid-1;
            }
            d[p]=i;
            if(p>q)
                q=p;
        }
        s+=q;
    }
    fout<<s;
    fin.close();fout.close();
    return 0;
}