Cod sursa(job #1001108)

Utilizator Andrei1998Andrei Constantinescu Andrei1998 Data 24 septembrie 2013 15:24:59
Problema Zoo Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 5.44 kb
#include <iostream>
#include <algorithm>

using namespace std;

struct elem
{
    int val;
    int poz;
}x[16005],rx[16005],y[16005],ry[16005],incep_x[100005],incep_y[100005],sfar_x[100005],sfar_y[100005];
elem rincep_x[100005],rincep_y[100005],rsfar_x[100005],rsfar_y[100005];

bool operator<(const elem &a,const elem &b)
{
    if(a.val<=b.val)
        return 1;
    return 0;
}

#define inf 10000 //de mod

struct elemul
{
    int val;
    int poz;
    int unde;
}cx[216015],cy[216015],fx[216015],fy[216015];

int main()
{
    int n,m,i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>x[i].val>>y[i].val;
        x[i].poz=i;
        y[i].poz=i;
        rx[i]=x[i];
        ry[i]=y[i];
    }
    sort(x+1,x+n+1);
    sort(y+1,y+n+1);

    cin>>m;
    for(i=1;i<=m;i++)
    {
        cin>>incep_x[i].val>>incep_y[i].val>>sfar_x[i].val>>sfar_y[i].val;
        incep_x[i].poz=i;
        incep_y[i].poz=i;
        sfar_x[i].poz=i;
        sfar_y[i].poz=i;
        rincep_x[i]=incep_x[i];
        rincep_y[i]=incep_y[i];
        rsfar_x[i]=sfar_x[i];
        rsfar_y[i]=sfar_y[i];
    }
    sort(incep_x+1,incep_x+m+1);
    sort(incep_y+1,incep_y+m+1);
    sort(sfar_x+1,sfar_x+m+1);
    sort(sfar_y+1,sfar_y+m+1);
    x[0].val=-inf;
    y[0].val=-inf;
    x[n+1].val=inf;
    y[n+1].val=inf;

    int t=0;
    for(i=1;i<=m;i++)
    {
        while(x[t+1].val<incep_x[i].val)
            t++;
        cout<<"pentru "<<incep_x[i].val<<' ';
        rincep_x[incep_x[i].poz]=x[t+1];
        cout<<x[t+1].val<<' ';
    }
    cout<<endl;
    t=0;
    for(i=1;i<=m;i++)
    {
        while(y[t+1].val<incep_y[i].val)
            t++;
        rincep_y[incep_y[i].poz]=y[t+1];
        cout<<y[t+1].val<<' ';
    }
    cout<<endl;
    //
    t=0;
    for(i=1;i<=m;i++)
    {
        while(x[t+1].val<=sfar_x[i].val)
            t++;
        rsfar_x[sfar_x[i].poz]=x[t];
        cout<<"pentru "<<sfar_x[i].val<<' ';
        cout<<x[t].val<<' ';
    }
    cout<<endl;
    t=0;
    for(i=1;i<=m;i++)
    {
        while(y[t+1].val<=sfar_y[i].val)
            t++;
        rsfar_y[sfar_y[i].poz]=y[t];
        cout<<y[t].val<<' ';
    }
    //cout<<endl;
    sort(x+1,x+n+1);
    sort(y+1,y+n+1);



    /*int rasp=1;
    int ante=x[1].val;
    for(i=1;i<=n;i++)
    {
        if(x[i].val!=ante)
        {
            ante=x[i].val;
            rasp++;
        }
        x[i].val=rasp;
        rx[x[i].poz].val=rasp;
    }

    rasp=1;
    ante=y[1].val;
    for(i=1;i<=n;i++)
    {
        if(y[i].val!=ante)
        {
            ante=y[i].val;
            rasp++;
        }
        y[i].val=rasp;
        ry[y[i].poz].val=rasp;
    }*/

    int acum=1;
    i=1;
int    j=1;
    while(i<=m && j<=m)
        if(incep_x[i]<sfar_x[j])
        {
            cx[acum].poz=incep_x[i].poz;
            cx[acum].unde=1;
            cx[acum++].val=incep_x[i++].val;
        }
        else
        {
            cx[acum].poz=sfar_x[i].poz;
            cx[acum].unde=2;
            cx[acum++].val=sfar_x[j++].val;
        }
    while(i<=m)
    {
        cx[acum].poz=incep_x[i].poz;
        cx[acum].unde=1;
        cx[acum++].val=incep_x[i++].val;
    }
    while(j<=m)
    {
        cx[acum].poz=sfar_x[j].poz;
        cx[acum].unde=2;
        cx[acum++].val=sfar_x[j++].val;
    }

    acum=1;
    i=1;
    j=1;
    while(i<=(2*m) && j<=n)
        if(cx[i].val<x[j].val)
        {
            fx[acum].poz=cx[acum].poz;
            fx[acum].unde=cx[acum].unde;
            fx[acum++].val=cx[i++].val;
        }
        else
        {
            fx[acum].poz=x[j].poz;
            fx[acum].unde=0;
            fx[acum++].val=x[j++].val;
        }
    while(i<=(2*m))
    {
        fx[acum].poz=cx[acum].poz;
        fx[acum].unde=cx[acum].unde;
        fx[acum++].val=cx[i++].val;
    }
    while(j<=n)
    {
        fx[acum].poz=x[j].poz;
        fx[acum].unde=0;
        fx[acum++].val=x[j++].val;
    }
    /////////////////////////////////////////////////////////////////////////////////
    acum=1;
    i=1;
    j=1;
    while(i<=m && j<=m)
        if(incep_y[i].val<sfar_y[j].val)
        {
            cy[acum].poz=incep_y[i].poz;
            cy[acum].unde=1;
            cy[acum++].val=incep_y[i++].val;
        }
        else
        {
            cy[acum].poz=sfar_y[i].poz;
            cy[acum].unde=2;
            cy[acum++].val=sfar_y[j++].val;
        }
    while(i<=m)
    {
        cy[acum].poz=incep_y[i].poz;
        cy[acum].unde=1;
        cy[acum++].val=incep_y[i++].val;
    }
    while(j<=m)
    {
        cy[acum].poz=sfar_y[j].poz;
        cy[acum].unde=2;
        cy[acum++].val=sfar_y[j++].val;
    }
/////////////
    acum=1;
    i=1;
    j=1;
    while(i<=(2*m) && j<=n)
        if(cy[i].val<y[j].val)
        {
            fy[acum].poz=cy[acum].poz;
            fy[acum].unde=cy[acum].unde;
            fy[acum++].val=cy[i++].val;
        }
        else
        {
            fy[acum].poz=y[j].poz;
            fy[acum].unde=0;
            fy[acum++].val=y[j++].val;
        }
    while(i<=(2*m))
    {
        fy[acum].poz=cx[acum].poz;
        fy[acum].unde=cx[acum].unde;
        fy[acum++].val=cx[i++].val;
    }
    while(j<=n)
    {
        fy[acum].poz=y[j].poz;
        fy[acum].unde=0;
        fy[acum++].val=y[j++].val;
    }

    for(i=1;i<=(n+2*m);i++)
    {

    }

    return 0;
}