Cod sursa(job #1146807)

Utilizator marta_diannaFII Filimon Marta Diana marta_dianna Data 19 martie 2014 12:07:39
Problema Pachete Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.73 kb
#include<fstream>
#include<algorithm>
#define NMAX 50010

using namespace std;

struct punct
{
    int x, y;
}c1[NMAX], c2[NMAX], c3[NMAX], c4[NMAX], O;
int n, n1, n2, n3, n4, nv, v[NMAX], sol=0;

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

void Plaseaza(punct A)
{
    if (A.x>O.x && A.y>O.y) c1[++n1]=A;
    else
        if (A.x>O.x && A.y<O.y)
        {
            A.y=2*O.y-A.y;
            c4[++n4]=A;
        }
        else
            if (A.y>O.y)
            {
                A.x=2*O.x-A.x;
                c2[++n2]=A;
            }
            else
            {
                A.y=2*O.y-A.y;
                A.x=2*O.x-A.x;
                c3[++n3]=A;
            }
}

void Citeste()
{
    int i;
    punct aux;

    f>>n>>O.x>>O.y;

    for (i=1; i<=n; ++i)
    {
        f>>aux.x>>aux.y;
        Plaseaza(aux);
    }
}

bool cmp(punct A, punct B)
{
    return A.y<B.y;
}

void Initializeaza()
{
    int i;
    for (i=1; i<=nv; ++i) v[i]=0;
    nv=0;
}

int cauta(int x)
{
    int st=1, dr=nv, mij, sol=0;

    while (st<=dr)
    {
        mij=(st+dr)/2;

        if (v[mij]>x) st=mij+1;
        else
        {
            dr=mij-1;
            sol=mij;
        }
    }

    return sol;
}

void Solve(punct a[], int n)
{
    int i, c;

    Initializeaza();

    sort(a+1, a+n+1, cmp);

    for (i=1; i<=n; ++i)
    {
        c=cauta(a[i].x);

        if (c==0) v[++nv]=a[i].x;
        else v[c]=a[i].x;
    }

    sol+=nv;
}

void Scrie()
{
    g<<sol<<"\n";
}

int main()
{
    Citeste();

    Solve(c1, n1);
    Solve(c2, n2);
    Solve(c3, n3);
    Solve(c4, n4);

    Scrie();

    f.close();
    g.close();
    return 0;
}