Cod sursa(job #1947980)

Utilizator Alex.PAlexandru Pacurar Alex.P Data 31 martie 2017 16:13:25
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>

using namespace std;

struct pct{
    int x;
    int y;
};

int cmp(pct a, pct b){
    if(a.x>b.x)
        return 1;
    return 0;
}

pct v[4][50000];
int size[4];

int coada[50002];

int cauta(int x, int dr){
    int st=0,mij;
    while(st<=dr){
        mij=(st+dr)/2;
        if(coada[mij]<x)
            st=mij+1;
        else
            dr=mij-1;
    }
    return st;
}

int main()
{
    FILE *fin, *fout;
    int n,ox,oy,i,j,k,l;
    fin=fopen("pachete.in","r");
    fout=fopen("pachete.out","w");
    fscanf(fin,"%d",&n);
    fscanf(fin,"%d%d",&ox,&oy);
    for(k=0;k<n;k++){
        fscanf(fin,"%d%d",&i,&j);
        i-=ox;
        j-=oy;
        if(i>0){
            if(j>0){
                v[0][size[0]].x=i;
                v[0][size[0]].y=j;
                size[0]++;
            }else{
                v[1][size[1]].x=i;
                v[1][size[1]].y=-j;
                size[1]++;
            }
        }else{
            if(j<0){
                v[2][size[2]].x=-i;
                v[2][size[2]].y=-j;
                size[2]++;
            }else{
                v[3][size[3]].x=-i;
                v[3][size[3]].y=j;
                size[3]++;
            }
        }
    }
    int suma=0;
    for(k=0;k<4;k++){
        int l=0,poz;
        sort(v[k],v[k]+size[k],cmp);
        for(i=0;i<size[k];i++){
            poz=cauta(v[k][i].y,l);
            coada[poz]=v[k][i].y;
            if(poz>l)
                l=poz;
        }
        suma+=l;
        printf("%d ",l);
        for(i=0;i<size[k]+1;i++){
            coada[i]=0;
        }
    }
    fprintf(fout,"%d",suma);
    fclose(fin);
    fclose(fout);
    return 0;
}