Cod sursa(job #1831312)

Utilizator Bodo171Bogdan Pop Bodo171 Data 17 decembrie 2016 20:19:53
Problema Pachete Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <iostream>
#include <fstream>
#include<algorithm>
using namespace std;
const int nmax=50005;
struct poinT
{
    int x,y;
}v[4][nmax];
bool comp(poinT unu,poinT doi)
{
    return unu.x<doi.x;
}
int a[nmax];
int p,poz,lgmax,N,X,Y,ox,oy,cadran,nr,distante,i,n[4];
void cb()
{
    poz=0;
    for(p=lgmax;p>=0;p--)
    {
       if(poz+(1<<p)<=nr&&a[poz+(1<<p)]>v[cadran][i].y)
        poz+=(1<<p);
    }
    poz++;
    a[poz]=v[cadran][i].y;
    if(poz>nr) nr=poz;
}
int main()
{
    ifstream f("pachete.in");
    ofstream g("pachete.out");
    f>>N>>ox>>oy;
    for(i=1;i<=N;i++)
    {
        f>>X>>Y;
        cadran=0;
        if(X>ox)
        {
            if(Y>oy) cadran=0;
            else {cadran=3;Y=oy-Y;}
        }
        else
        {
            X=ox-X;
            if(Y>oy) cadran=1;
            else {cadran=2;Y=oy-Y;}
        }
        n[cadran]++;
        v[cadran][n[cadran]].x=X;
        v[cadran][n[cadran]].y=Y;
    }
    for(cadran=0;cadran<4;cadran++)
    {
        sort(v[cadran]+1,v[cadran]+n[cadran]+1,comp);
        nr=0;lgmax=1;
        while((1<<lgmax)<=n[cadran])
            lgmax++;
        for(i=1;i<=n[cadran];i++)
             cb();
        distante+=nr;
    }
    g<<distante;
    return 0;
}