Cod sursa(job #542041)

Utilizator ilucianIlea Lucian ilucian Data 25 februarie 2011 18:39:18
Problema Reuniune Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <fstream>
#include <algorithm>
#include <iostream>

using namespace std;
typedef struct {long long xst,yst,xdr,ydr;} DR;
DR D[4];
long long i,j;
long long P, A;
long long X[20],Y[20];
long long n;
long long st, dr;

ifstream fi("reuniune.in");
ofstream fo("reuniune.out");

void citeste(DR & D)
{
    fi>>D.xst>>D.yst>>D.xdr>>D.ydr;
}

int f1(DR d1, DR d2)
// pentru ordonare dupa x
{
    if (d1.xst<=d2.xst)
        return 1;
    return 0;
}

long long maxi(long long a, long long b)
{
    if (a>=b)
        return a;
    return b;
}

int f2(DR d1, DR d2)
{
    if (d1.yst<=d2.yst)
        return 1;
    return 0;
}

int main()
{
    for (i=1;i<=3;i++)
        citeste(D[i]);
    sort(D+1,D+4,f1);
    // se proiecteaza varfurile dreptunghiurilor pe Oy
    n=0;
    for (i=1;i<=3;i++)
    {
        Y[++n]=D[i].yst;
        Y[++n]=D[i].ydr;
    }
    sort(Y+1,Y+n+1);
    for (i=1;i<=n-1;i++)
    {
        // se intersecteaza banda Y[i]-Y[i+1] cu toate dreptunghiurile
        st=dr=-2000000000;
        for (j=1;j<=3;j++)
            if (D[j].yst<=Y[i] && D[j].ydr>=Y[i+1])
                if (dr<D[j].xst)
                    if (st!=dr)
                    {
                        A+=(Y[i+1]-Y[i])*(dr-st);
                        P+=(2*(Y[i+1]-Y[i]));
                        st=D[j].xst;
                        dr=D[j].xdr;
                    }
                    else
                    {
                        st=D[j].xst;
                        dr=D[j].xdr;
                    }
                else
                        dr=maxi(dr,D[j].xdr);
        if (st!=dr)
        {
            A+=(Y[i+1]-Y[i])*(dr-st);
            P+=(2*(Y[i+1]-Y[i]));
        }
    }
    sort(D+1,D+4,f2);
    // se proiecteaza varfurile dreptunghiurilor pe Ox
    n=0;
    for (i=1;i<=3;i++)
    {
        X[++n]=D[i].xst;
        X[++n]=D[i].xdr;
    }
    sort(X+1,X+n+1);
    for (i=1;i<=n-1;i++)
    {
        // se intersecteaza banda X[i]-X[i+1] cu toate dreptunghiurile
        st=dr=-2000000000;
        for (j=1;j<=3;j++)
            if (D[j].xst<=X[i] && D[j].xdr>=X[i+1])
                if (dr<D[j].yst)
                    if (st!=dr)
                    {
                        P+=(2*(X[i+1]-X[i]));
                        st=D[j].yst;
                        dr=D[j].ydr;
                    }
                    else
                    {
                        st=D[j].yst;
                        dr=D[j].ydr;
                    }
                else
                        dr=maxi(dr,D[j].ydr);
        if (st!=dr)
            P+=(2*(X[i+1]-X[i]));
    }
    fo<<A<<" "<<P;
    fi.close();
    fo.close();
    return 0;
}