Cod sursa(job #542042)

Utilizator veleanduAlex Velea veleandu Data 25 februarie 2011 18:39:19
Problema Reuniune Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.89 kb
#include<fstream>
#include<iostream>
using namespace std;

typedef struct { long long x0,y0,x1,y1; } coord;
coord D[4];
long long i;
long long X[50],Y[50],p,a,st,dr,n,j;

bool mysortx (coord x, coord y)
{
    if(x.x0==y.x0)
    {
        if(x.y0==y.y0)
            return 1;
        if(x.y0<y.y0)
            return 1;
        else
            return 0;
    }
    if(x.x0<y.x0)
        return 1;
    else
        return 0;

}
long long maxi(long long a, long long b)
{
    if(a>b)
         return a;
     return b;
}
bool mysorty (coord x, coord y)
{
    if(x.y0==y.y0)
    {
        if(x.x0==y.x0)
            return 1;
        if(x.x0<y.x0)
            return 1;
        else
            return 0;
    }
    if(x.y0<y.y0)
        return 1;
    else
        return 0;

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

    for( i=1; i<=3; ++i)
        in>>D[i].x0>>D[i].y0>>D[i].x1>>D[i].y1;

    sort(D+1,D+4,mysortx);
    p=0;
    a=0;
    n=0;
    for(i=1; i<=3; ++i)
    {
        Y[++n]=D[i].y0;
        Y[++n]=D[i].y1;
    }
    sort(Y+1,Y+n+1);
    for(i=1; i<n; ++i)
    {
        /// se intersecteaza banda curenta cu toate dreptuncgiurile :D .. Y[i] cu Y[i+1]
        dr=st=-2000000000;
        for(j=1; j<=3; ++j)
            if(D[j].y0<=Y[i] && D[j].y1>=Y[i+1])
                if(dr<D[j].x0)
                    if(st!=dr)
                    {
                        a+=(Y[i+1]-Y[i])*(dr-st);
                        p+=2*(Y[i+1]-Y[i]);
                        st=D[j].x0;
                        dr=D[j].x1;
                    }
                    else
                    {
                        st=D[j].x0;
                        dr=D[j].x1;
                    }
                else{
                        dr=maxi(dr,D[j].x1);
                }
        if(st!=dr)
        {
            p+=2*(Y[i+1]-Y[i]);
            a+=(Y[i+1]-Y[i])*(dr-st);
        }
    }
    sort(D+1,D+4,mysorty);
    n=0;
    for(i=1; i<=3; ++i)
    {
        X[++n]=D[i].x0;
        X[++n]=D[i].x1;
    }
    sort(X+1,X+n+1);
    for(i=1; i<n; ++i)
    {
        /// se intersecteaza banda curenta cu toate dreptuncgiurile :D .. Y[i] cu Y[i+1]
        dr=st=-2000000000;
        for(j=1; j<=3; ++j)
            if(D[j].x0<=X[i] && D[j].x1>=X[i+1])
                if(dr<D[j].y0)
                    if(st!=dr)
                    {
                        p+=2*(X[i+1]-X[i]);
                        st=D[j].y0;
                        dr=D[j].y1;
                    }
                    else
                    {
                        st=D[j].y0;
                        dr=D[j].y1;
                    }
                else{
                        dr=maxi(dr,D[j].y1);
                }
        if(st!=dr)
            p+=2*(X[i+1]-X[i]);
    }
    out<<a<<" "<<p;
    return 0;
}