Cod sursa(job #779533)

Utilizator tester9x9Tester9x9 tester9x9 Data 17 august 2012 22:55:25
Problema Reuniune Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <fstream>
#include <cstring>
#include <algorithm>
#define LL long long

using namespace std;

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

struct Drept
{
    LL x1,y1,x2,y2;
};

Drept A,B,C;
Drept AxB,AxC,BxC,AxBxC;

LL S,P;

LL M[20][20];
LL X[20],Y[20],x,y;

void Update (const Drept& A)
{
    for (int i=A.x1; i<=A.x2; i++)
        for (int j=A.y1; j<=A.y2; j++)
            M[i][j]++;
}

LL Area (const Drept &A)
{
    return max(0LL,(A.x2-A.x1)*(A.y2-A.y1));
}

Drept Reunite (const Drept& A, const Drept& B)
{
    Drept R;
    R.x1=max(A.x1,B.x1);
    R.x2=min(A.x2,B.x2);
    R.y1=max(A.y1,B.y1);
    R.y2=min(A.y2,B.y2);

    memset(M,0,sizeof(M));
    x=y=0;
    X[++x]=A.x1;
    Y[++y]=A.y1;
    X[++x]=A.x2;
    Y[++y]=A.y2;
    X[++x]=B.x1;
    Y[++y]=B.y1;
    X[++x]=B.x2;
    Y[++y]=B.y2;

    sort(X+1,X+x+1);
    sort(Y+1,Y+y+1);
    X[0]=Y[0]=1;
    for (int i=2; i<=x; i++)
        if (X[i]!=X[i-1])
            X[++X[0]]=X[i];
    for (int i=2; i<=y; i++)
        if (Y[i]!=Y[i-1])
            Y[++Y[0]]=Y[i];

    x=X[0];
    y=Y[0];
    Drept C,D;

    for (int i=1; i<=x; i++)
    {
        if (A.x1==X[i]) C.x1=i;
        if (A.x2==X[i]) C.x2=i;
        if (B.x1==X[i]) D.x1=i;
        if (B.x2==X[i]) D.x2=i;
    }
    for (int i=1; i<=y; i++)
    {
        if (A.y1==Y[i]) C.y1=i;
        if (A.y2==Y[i]) C.y2=i;
        if (B.y1==Y[i]) D.y1=i;
        if (B.y2==Y[i]) D.y2=i;
    }
    Update(C);
    Update(D);

    int XMin=100,YMin=100;
    int XMax=0,YMax=0;
    for (int i=1; i<10; i++)
        for (int j=1; j<10; j++)
            if (M[i][j]>1)
            {
                XMin=min(XMin,i);
                XMax=max(XMax,i);
                YMin=min(YMin,i);
                YMax=max(YMax,i);
            }

    if (XMin>XMax || YMin>YMax)
        XMin=XMax=YMin=YMax=0;

    Drept AUX;
    AUX.x1=X[XMin];
    AUX.x2=X[XMax];
    AUX.y1=Y[YMin];
    AUX.y2=Y[YMax];

    AUX.x1=max(AUX.x1,R.x1);
    AUX.x2=min(AUX.x2,R.x2);
    AUX.y1=max(AUX.y1,R.y1);
    AUX.y2=min(AUX.y2,R.y2);
    return AUX;
}

LL Perimeter (const Drept &A)
{
    return max(0LL,2*(A.x2-A.x1+A.y2-A.y1));
}

int main ()
{
    f >> A.x1 >> A.y1 >> A.x2 >> A.y2;
    f >> B.x1 >> B.y1 >> B.x2 >> B.y2;
    f >> C.x1 >> C.y1 >> C.x2 >> C.y2;

    AxB=Reunite(A,B);
    AxC=Reunite(A,C);
    BxC=Reunite(B,C);

    AxBxC=Reunite(AxB,C);

    S=Area(A)+Area(B)+Area(C)-Area(AxB)-Area(AxC)-Area(BxC)+Area(AxBxC);
    P=Perimeter(A)+Perimeter(B)+Perimeter(C)-Perimeter(AxB)-Perimeter(AxC)-Perimeter(BxC)+Perimeter(AxBxC);

    g << S << ' ' << P << '\n';
    f.close();
    g.close();
    return 0;
}