Tuenti Contest 15 (Pablo Moreno)

/*
    Author: Pablo Moreno Olalla
    Email address: darthbrevu@yahoo.es
*/
#include <map>
#include <list>
#include <cstdio>
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>

using namespace std;

class Rectangle {
public:
    int lx,ly,ux,uy;
    inline Rectangle()  {}
    inline Rectangle(int llx,int lly,int uux,int uuy):lx(llx),ly(lly),ux(uux),uy(uuy)   {}
    inline int area() const {
        return (ux-lx)*(uy-ly);
    };
    bool isValid() const    {
        return (ux>lx)&&(uy>ly);
    }
    bool isDisjoint(const Rectangle &r) const   {
        return (lx>=r.ux)||(ly>=r.uy)||(r.lx>=ux)||(r.ly>=uy);
    }
};

inline void substract(const Rectangle &r1,const Rectangle &r2,list<Rectangle> &out) {
    //This is the main method of the program.
    if ((r1.lx>=r2.ux)||(r1.ly>=r2.uy)||(r2.lx>=r1.ux)||(r2.ly>=r1.uy)) {
        out.push_back(r1);
        return;
    }
    int lx=max(r1.lx,r2.lx);
    int ux=min(r1.ux,r2.ux);
    Rectangle a(r1.lx,r1.ly,r2.lx,r1.uy);
    Rectangle b(lx,r1.ly,ux,r2.ly);
    Rectangle c(lx,r2.uy,ux,r1.uy);
    Rectangle d(r2.ux,r1.ly,r1.ux,r1.uy);
    if (a.isValid()) out.push_back(a);
    if (b.isValid()) out.push_back(b);
    if (c.isValid()) out.push_back(c);
    if (d.isValid()) out.push_back(d);
    return;
}

inline void fullSubstract(const list<Rectangle> &l1,const Rectangle &r2,list<Rectangle> &l3)    {
    //We don't care about the colour, because we'll insert r2 into the proper place at the end :).
    l3.clear();
    list<Rectangle> tmp;
    for (list<Rectangle>::const_iterator it=l1.begin();it!=l1.end();++it)   {
        substract(*it,r2,tmp);
        l3.splice(l3.end(),tmp);
    }
}

int main(int argc,char **argv)  {
    //The first two lines are not strictly necessary, but make the code a little more handy.
    if (argc>=2) freopen(argv[1],"r",stdin);
    if (argc>=3) freopen(argv[2],"w",stdout);
    string tmp;
    string s1,s2,s3;
    do  {
        getline(cin,tmp);
        istringstream iss(tmp);
        int W,L,N;
        iss>>W>>L>>N;
        if (iss.fail()) break;
        map<int,list<Rectangle> > colours;  //A multimap could have been used, but I feel this is better for this case.
        Rectangle r;
        r.lx=0;
        r.ly=0;
        r.ux=W;
        r.uy=L;
        colours[1].push_back(r);
        int colour;
        list<Rectangle> tmpRects;
        for (unsigned int i=0;i<N;++i)  {
            iss>>r.lx>>r.ly>>r.ux>>r.uy>>colour;
            if (iss.fail()) break;
            //Before doing anything, let's trim it, so that we only paint over the canvas.
            r.lx=max(0,r.lx);
            r.ly=max(0,r.ly);
            r.ux=min(W,r.ux);
            r.uy=min(L,r.uy);
            if (r.lx>=r.ux||r.ly>=r.uy) break;  //Wrongly defined rectangle.
            for (map<int,list<Rectangle> >::iterator it=colours.begin();it!=colours.end();++it) {
                //This loop would have been a little bit more complicated with a multimap...
                fullSubstract(it->second,r,tmpRects);
                it->second=tmpRects;    //... mostly because of this instruction.
            }
            colours[colour].push_back(r);   //The list will be created if it doesn't exist. That's how a map works.
        }
        //This would have required the use of equal_range, if a multimap had been chosen.
        bool anyWritten=false;
        for (map<int,list<Rectangle> >::const_iterator it=colours.begin();it!=colours.end();++it)   {
            int area=0;
            for (list<Rectangle>::const_iterator lIt=it->second.begin();lIt!=it->second.end();++lIt) area+=lIt->area();
            if (area>0) {
                if (anyWritten) cout<<' ';
                cout<<it->first<<' '<<area;
                anyWritten++;
            }
        }
        cout<<endl;
    }   while (!cin.eof());
    return 0;
}