Cod sursa(job #1152393)

Utilizator alex_HarryBabalau Alexandru alex_Harry Data 24 martie 2014 18:12:49
Problema Pachete Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#include <fstream>
#include <algorithm>
using namespace std;
ifstream f("pachete.in");
ofstream g("pachete.out");
int N,Result;
int length1,length2,length3,length4;
struct Element{
int value;
int pozition;
int next;
int pred;
} Aux[50005];
int Pozition[50005];
struct Point{
int x;
int y;
} Cadran1[50005],Cadran2[50005],Cadran3[50005],Cadran4[50005];
int initiala,initialo;
void Fill_Cadran(int abs,int ord)
{
    if(abs<initiala && ord>initialo)
        Cadran1[++length1].x=abs,Cadran1[length1].y=ord;
    if(abs>=initiala && ord>initialo)
        Cadran2[++length2].x=abs,Cadran2[length2].y=ord;
    if(abs<initiala && ord<=initialo)
        Cadran3[++length3].x=abs,Cadran3[length3].y=ord;
    if(abs>=initiala && ord<=initialo)
        Cadran4[++length4].x=abs,Cadran4[length4].y=ord;
}
inline bool compare2(Element a,Element b)
{
    if(a.value==b.value)
        return a.pozition<b.pozition;
    return a.value<b.value;
}
void Read()
{
    int i;
    f>>N;
    f>>initiala>>initialo;
    for(i=1;i<=N;i++)
    {
        int abs,ord;
        f>>abs>>ord;
        Fill_Cadran(abs,ord);
    }
}
inline bool compare(Point a,Point b)
{
    if(a.x==b.x)
        return a.y<b.y;
    return a.x<b.x;
}
void Sort_Arrays()
{
    sort(Cadran1+1,Cadran1+length1+1,compare);
    sort(Cadran2+1,Cadran2+length2+1,compare);
    sort(Cadran3+1,Cadran3+length3+1,compare);
    sort(Cadran4+1,Cadran4+length4+1,compare);
}
int Solve_Cadran(Point Cadran[],int N)
{
    int result=0;
    for(int i=1;i<=N;i++)
        Aux[i].value=Cadran[i].y,Aux[i].pozition=i;
    sort(Aux+1,Aux+N+1,compare2);
    for(int i=1;i<=N;i++)
        Aux[i].pred=i-1,Aux[i].next=i+1,Pozition[Aux[i].pozition]=i;
    for(int i=1;i<=N;i++)
    {
        if(Aux[Pozition[i]].pred==0)
        {
            result++;
            Aux[Aux[Pozition[i]].next].pred=0;
        }
        else
        {
            Aux[Aux[Pozition[i]].next].pred=Aux[Pozition[i]].pred;
            Aux[Aux[Pozition[i]].pred].next=Aux[Pozition[i]].next;
        }
    }
    return result;
}
int main()
{
    Read();
    Sort_Arrays();
    Result+=Solve_Cadran(Cadran1,length1);
    Result+=Solve_Cadran(Cadran2,length2);
    Result+=Solve_Cadran(Cadran3,length3);
    Result+=Solve_Cadran(Cadran4,length4);
    g<<Result<<"\n";
    return 0;
}