Cod sursa(job #2430430)

Utilizator mjmilan11Mujdar Milan mjmilan11 Data 14 iunie 2019 20:09:59
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("pachete.in");
ofstream fout("pachete.out");

const int NMAX = 50005;
int n,v[NMAX];

struct punct
{
    int x,y;
};

punct a[5][NMAX];

bool cmp(punct a,punct b)
{
    if(a.x==b.x) return a.y<b.y;
    return a.x<b.x;
}

int rez_cadran(punct cad[],int nr)
{
    sort(cad+1,cad+nr+1,cmp);
    int rasp=0;
    for(int i=1;i<=nr;i++)
    {
        int j=0;
        for(int p=(1<<15);p!=0;p/=2)
        {
            if(j+p<=rasp and v[j+p]>cad[i].y) j+=p;
        }
        j++;
        if(j>rasp) v[++rasp]=cad[i].y;
        else v[j]=cad[i].y;
    }
    return rasp;
}

int main()
{
    int x0,y0;
    fin >> n;
    fin >> x0 >> y0;
    int x1,y1,c1=0,c2=0,c3=0,c4=0;
    for(int i=1;i<=n;i++)
    {
        fin >> x1 >> y1;
        x1-=x0;
        y1-=y0;
        if(x1>=0 and y1>=0) a[1][++c1]={x1,y1};      /// C1
        else if(x1>=0 and y1<0) a[2][++c2]={x1,-y1}; /// C2
        else if(x1<0 and y1<0) a[3][++c3]={-x1,-y1}; /// C3
        else if(x1<0 and y1>=0) a[4][++c4]={-x1,y1}; /// C4
    }
    fout << rez_cadran(a[1],c1)+rez_cadran(a[2],c2)+rez_cadran(a[3],c3)+rez_cadran(a[4],c4);
    return 0;
}