Cod sursa(job #2379608)

Utilizator VasileAmbreiajVasile Ambreiaj VasileAmbreiaj Data 13 martie 2019 20:57:18
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <bits/stdc++.h>

using namespace std;

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

int n,ox,oy,i,j,nrd,nrdrin;
int coord[50001];

struct str{
    int x,y,l;
    bool fol;
}v[5][50001];

bool cond(str a, str b){
    if(a.x!=b.x)
        return a.x<b.x;
    return a.y<b.y;
}

void caubin(int zona, int ind){
    int s=1,d=nrdrin,m,poz=nrdrin+1;

    while(s<=d){
        m=(s+d)/2;

        if(v[zona][ind].y>=coord[m]){
            poz=m;
            d=m-1;
        } else s=m+1;
    }

    coord[poz]=v[zona][ind].y;
    if(poz>nrdrin)
        ++nrdrin;
}

int main()
{
    f>>n>>ox>>oy;
    int x,y;

    for(i=1;i<=n;++i){
        f>>x>>y;

        if(x>=ox && y>=oy){
            ++v[1][0].l;
            v[1][v[1][0].l].x=x-ox;
            v[1][v[1][0].l].y=y-oy;
        } else if(x>=ox && y<=oy){
            ++v[2][0].l;
            v[2][v[2][0].l].x=x-ox;
            v[2][v[2][0].l].y=oy-y;
        } else if(x<=ox && y<=oy){
            ++v[3][0].l;
            v[3][v[3][0].l].x=ox-x;
            v[3][v[3][0].l].y=oy-y;
        } else if(x<=ox && y>=oy){
            ++v[4][0].l;
            v[4][v[4][0].l].x=ox-x;
            v[4][v[4][0].l].y=y-oy;
        }
    }

    for(i=1;i<=4;++i){
        sort(v[i]+1,v[i]+v[i][0].l+1,cond);
        memset(coord,0,sizeof(coord));
        nrdrin=0;

        for(j=1;j<=v[i][0].l;++j){
            caubin(i,j);
        }

        nrd+=nrdrin;
    }

    g<<nrd;

    return 0;
}