Cod sursa(job #1139306)

Utilizator AlexandruValeanuAlexandru Valeanu AlexandruValeanu Data 10 martie 2014 23:44:07
Problema Reuniune Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.17 kb
#include <iostream>
#include <fstream>

using namespace std;

const int Nmax = 4;
const long long inf = 1e18;

struct Point
{
    long long x, y;

    Point( const long long _x = 0, const long long _y = 0 ) : x( _x ), y( _y ) {}

    bool operator <= ( const Point P ) const
    {
        return ( x <= P.x && y <= P.y );
    }

    friend istream& operator >> ( istream &f, Point &P )
    {
        f >> P.x >> P.y;
        return f;
    }
};

struct Rectangle
{
    Point SJ, DS;

    Rectangle( const Point _A = Point( 0, 0 ), const Point _B = Point( 0, 0 ) )
    {
        SJ = _A;
        DS = _B;
    }

    friend istream& operator >> ( istream &f, Rectangle &R )
    {
        f >> R.SJ >> R.DS;
        return f;
    }
};

Rectangle v[Nmax];
int N;

template <class T>
T abs( T x )
{
    return x > 0 ? +x : -x;
}

Rectangle I( const Rectangle A, const Rectangle B )
{
    Point SJ, DS;

    SJ.x = max( A.SJ.x, B.SJ.x );
    SJ.y = max( A.SJ.y, B.SJ.y );

    DS.x = min( A.DS.x, B.DS.x );
    DS.y = min( A.DS.y, B.DS.y );

    if ( SJ <= DS )
            return Rectangle( SJ, DS );
    else
            return Rectangle();
}

long long Area( Rectangle R )
{
    return ( abs( R.SJ.x - R.DS.x ) * abs( R.SJ.y - R.DS.y ) );
}

long long Perm( Rectangle R )
{
    return ( 2LL * ( abs( R.SJ.x - R.DS.x ) + abs( R.SJ.y - R.DS.y ) ) );
}

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

    N = 3;

    for ( int i = 1; i <= N; ++i )
            f >> v[i];

    long long A = 0, P = 0;
    int lim = 1 << N;

    for ( int i = 1; i < lim; ++i )
    {
        Rectangle R( Point( -inf, -inf ), Point( inf, inf ) );
        int nrb = 0;

        for ( int j = 0; j < N; ++j )
        {
            if ( i & ( 1 << j ) )
            {
                R = I( R, v[j + 1] );
                nrb++;
            }
        }

        if ( nrb % 2 )
        {
            A += Area( R );
            P += Perm( R );
        }
        else
        {
            A -= Area( R );
            P -= Perm( R );
        }
    }

    g << A << " " << P << "\n";

    return 0;
}