Cod sursa(job #1917290)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 9 martie 2017 11:53:09
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.51 kb
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("pachete.in");
ofstream g("pachete.out");

int n,i,j,xi,yi,x,y,suma,st,dr,mid,kk,k[5],u[50002];

struct abc
{
    int x,y;
}v[5][50002];

bool cmp(abc a, abc b)
{
    return a.x<b.x;
}

int main()
{
    f>>n>>xi>>yi;
    for(i=1;i<=n;i++)
    {
        f>>x>>y;
        x-=xi;
        yi-=yi;
        if(x>0)
        {
            if(y>0)
            {
                v[1][++k[1]].x=x;
                v[1][k[1]].y=y;
            }
            else
            {
                v[4][++k[4]].x=x;
                v[4][k[4]].y=-y;
            }
        }
        else
        {
            if(y>0)
            {
                v[2][++k[2]].x=-x;
                v[2][k[2]].y=y;
            }
            else
            {
                v[3][++k[3]].x=-x;
                v[3][k[3]].y=-y;
            }
        }
    }
    for(i=1;i<=4;i++)
    {
        sort(v[i]+1,v[i]+k[i]+1,cmp);
        u[1]=v[i][1].y;
        kk=1;
        for(j=2;j<=k[i];j++)
        {
            if(v[i][j].y<u[kk])
                u[++kk]=v[i][j].y;
            else
            {
                st=1;
                dr=kk;
                while(st<=dr)
                {
                    mid=(st+dr)/2;
                    if(u[mid]>v[i][j].y)
                    {
                        st=mid+1;
                    }
                    else dr=mid-1;
                }
                u[st]=v[i][j].y;
            }
            suma+=kk;
        }
    }
    g<<suma;
    return 0;
}