Cod sursa(job #2632274)

Utilizator Stefan_PiscuPiscu Stefan Constantin Stefan_Piscu Data 2 iulie 2020 17:34:40
Problema Pachete Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <bits/stdc++.h>
using namespace std;

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

struct point {long long x;long long y;};

point p,v[50005];

point k[4][50005];

int n, m, t[4];

long long s[50005];

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

int solve(point q[],int l){
  sort(q+1,q+l+1,cmp);
  m=0;
  for(int i=1;i<=l;i++) {
    int sol=0;
    for(int pas=1<<15;pas;pas>>=1)
      if(sol+pas<=m&&s[sol+pas]>q[i].y)
        sol+=pas;
    sol++;
    if(sol>m)
      s[++m]=q[i].y;
    else
      s[sol]=q[i].y;
  }
  return m;
}
int main()
{
  fin>>n;
  fin>>p.x>>p.y;
  for(int i=1;i<=n;i++) {
    fin>>v[i].x>>v[i].y;
    v[i].x-=p.x;
    v[i].y-=p.y;
    if(v[i].x>=0&&v[i].y>=0)
      k[0][++t[0]]=v[i];

    if(v[i].x<0&&v[i].y>=0) {
      v[i].x=-v[i].x;
      k[1][++t[1]]=v[i];
    }
    if(v[i].x>=0&&v[i].y<0) {
      v[i].y=-v[i].y;
      k[2][++t[2]]=v[i];
    }
    if(v[i].x<0&&v[i].y<0) {
      v[i].x=-v[i].x;
      v[i].y=-v[i].y;
      k[3][++t[3]]=v[i];
    }
  }
  fout<<solve(k[0],t[0])+solve(k[1],t[1])+solve(k[2],t[2])+solve(k[3],t[3])<<"\n";
  return 0;
}