Cod sursa(job #1252318)

Utilizator acomAndrei Comaneci acom Data 30 octombrie 2014 17:30:42
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.38 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream fin("pachete.in");
ofstream fout("pachete.out");
#define NMAX 50005
struct punct
{
    int x,y;
} aux,A[5][NMAX];
int n,k,x,y,x0,y0,cd,sol,a[5],v[NMAX];
int cadran(int x, int y)
{
    if (x>0)
    {
        if (y>0) return 1;
        else return 4;
    }
    else
    {
        if (y>0) return 2;
        else return 3;
    }
}
bool cmp(const punct &A, const punct &B)
{
    if (A.x==B.x) return (A.y<B.y);
    return (A.x<B.x);
}
int main()
{
    int i,j,st,dr,mij;
    fin>>n>>x0>>y0;
    for (i=1;i<=n;++i)
    {
        fin>>x>>y;
        x-=x0, y-=y0;
        aux.x=abs(x), aux.y=abs(y);
        cd=cadran(x,y);
        A[cd][++a[cd]]=aux;
    }
    for (i=1;i<5;++i)
        sort(A[i]+1,A[i]+a[i]+1,cmp);
    for (j=1;j<5;++j)
    {
        if (!a[j]) continue;
        v[k=1]=1;
        for (i=2;i<=a[j];++i)
        {
            if (A[j][i].y<A[j][v[k]].y)
            {
                v[++k]=i;
                continue;
            }
            st=1, dr=k;
            while (st<=dr)
            {
                mij=(st+dr)>>1;
                if (A[j][i].y<A[j][v[mij]].y)
                    dr=mij-1;
                else
                    st=mij+1;
            }
            v[dr]=i;
        }
        sol+=k;
    }
    fout<<sol<<"\n";
    return 0;
}