Cod sursa(job #1915419)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 8 martie 2017 20:58:19
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <fstream>
#include <algorithm>
#define DIM 50001
#define f first
#define s second
using namespace std;
int n,i,x,y,X,Y,k,k1,k2,k3,k4,sol,dim,st,dr,mid;
pair <int,int> a[DIM],b[DIM],c[DIM],d[DIM];
int v[DIM];
ifstream fin ("pachete.in");
ofstream fout ("pachete.out");
int functie (pair<int,int> A[DIM]){
    //if (dim == 0)
      //  return 0;
    sort (A+1,A+dim+1);
    k = 1;
    for (int i = 1;i<=dim;i++){
        st = 1;
        dr = k;
        while (st <= dr){
            mid = (st+dr)/2;
            if (v[mid] <= A[i].s)
                dr = mid-1;
            else
                st = mid+1;
        }
        if (st > k)
            k++;
        v[st] = A[i].s;
    }
    return k;
}
int main (){

    fin>>n>>X>>Y;
    for (i=1;i<=n;i++){
        fin>>x>>y;
        x -= X;
        y -= Y;
        if (x < 0){
            if (y < 0){
                c[++k3].f = x;
                c[k3].s = y;
            }
            else{
                a[++k1].f = x;
                a[k1].s = y;
            }
        }
        else{
            if (y < 0){
                d[++k4].f = x;
                d[k4].s = y;
            }
            else{
                b[++k2].f = x;
                b[k2].s = y;
            }
        }
    }
    dim = k2;
    sol += functie (b);
    for (i=1;i<=k1;i++)
        a[i].f -= a[i].f;
    dim = k1;
    sol += functie (a);
    for (i=1;i<=k3;i++){
        c[i].f -= c[i].f;
        c[i].s -= c[i].s;
    }
    dim = k3;
    sol += functie (c);
    for (i=1;i<=k4;i++)
        d[i].s -= d[i].s;
    dim = k4;
    sol + functie (d);
    fout<<sol;

    return 0;
}