Nbrevu

Tuenti Contest 15 (Pablo Moreno)

Jun 20th, 2011
1,073
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.     Author: Pablo Moreno Olalla
  3.     Email address: darthbrevu@yahoo.es
  4. */
  5. #include <map>
  6. #include <list>
  7. #include <cstdio>
  8. #include <string>
  9. #include <sstream>
  10. #include <iostream>
  11. #include <algorithm>
  12.  
  13. using namespace std;
  14.  
  15. class Rectangle {
  16. public:
  17.     int lx,ly,ux,uy;
  18.     inline Rectangle()  {}
  19.     inline Rectangle(int llx,int lly,int uux,int uuy):lx(llx),ly(lly),ux(uux),uy(uuy)   {}
  20.     inline int area() const {
  21.         return (ux-lx)*(uy-ly);
  22.     };
  23.     bool isValid() const    {
  24.         return (ux>lx)&&(uy>ly);
  25.     }
  26.     bool isDisjoint(const Rectangle &r) const   {
  27.         return (lx>=r.ux)||(ly>=r.uy)||(r.lx>=ux)||(r.ly>=uy);
  28.     }
  29. };
  30.  
  31. inline void substract(const Rectangle &r1,const Rectangle &r2,list<Rectangle> &out) {
  32.     //This is the main method of the program.
  33.     if ((r1.lx>=r2.ux)||(r1.ly>=r2.uy)||(r2.lx>=r1.ux)||(r2.ly>=r1.uy)) {
  34.         out.push_back(r1);
  35.         return;
  36.     }
  37.     int lx=max(r1.lx,r2.lx);
  38.     int ux=min(r1.ux,r2.ux);
  39.     Rectangle a(r1.lx,r1.ly,r2.lx,r1.uy);
  40.     Rectangle b(lx,r1.ly,ux,r2.ly);
  41.     Rectangle c(lx,r2.uy,ux,r1.uy);
  42.     Rectangle d(r2.ux,r1.ly,r1.ux,r1.uy);
  43.     if (a.isValid()) out.push_back(a);
  44.     if (b.isValid()) out.push_back(b);
  45.     if (c.isValid()) out.push_back(c);
  46.     if (d.isValid()) out.push_back(d);
  47.     return;
  48. }
  49.  
  50. inline void fullSubstract(const list<Rectangle> &l1,const Rectangle &r2,list<Rectangle> &l3)    {
  51.     //We don't care about the colour, because we'll insert r2 into the proper place at the end :).
  52.     l3.clear();
  53.     list<Rectangle> tmp;
  54.     for (list<Rectangle>::const_iterator it=l1.begin();it!=l1.end();++it)   {
  55.         substract(*it,r2,tmp);
  56.         l3.splice(l3.end(),tmp);
  57.     }
  58. }
  59.  
  60. int main(int argc,char **argv)  {
  61.     //The first two lines are not strictly necessary, but make the code a little more handy.
  62.     if (argc>=2) freopen(argv[1],"r",stdin);
  63.     if (argc>=3) freopen(argv[2],"w",stdout);
  64.     string tmp;
  65.     string s1,s2,s3;
  66.     do  {
  67.         getline(cin,tmp);
  68.         istringstream iss(tmp);
  69.         int W,L,N;
  70.         iss>>W>>L>>N;
  71.         if (iss.fail()) break;
  72.         map<int,list<Rectangle> > colours;  //A multimap could have been used, but I feel this is better for this case.
  73.         Rectangle r;
  74.         r.lx=0;
  75.         r.ly=0;
  76.         r.ux=W;
  77.         r.uy=L;
  78.         colours[1].push_back(r);
  79.         int colour;
  80.         list<Rectangle> tmpRects;
  81.         for (unsigned int i=0;i<N;++i)  {
  82.             iss>>r.lx>>r.ly>>r.ux>>r.uy>>colour;
  83.             if (iss.fail()) break;
  84.             //Before doing anything, let's trim it, so that we only paint over the canvas.
  85.             r.lx=max(0,r.lx);
  86.             r.ly=max(0,r.ly);
  87.             r.ux=min(W,r.ux);
  88.             r.uy=min(L,r.uy);
  89.             if (r.lx>=r.ux||r.ly>=r.uy) break;  //Wrongly defined rectangle.
  90.             for (map<int,list<Rectangle> >::iterator it=colours.begin();it!=colours.end();++it) {
  91.                 //This loop would have been a little bit more complicated with a multimap...
  92.                 fullSubstract(it->second,r,tmpRects);
  93.                 it->second=tmpRects;    //... mostly because of this instruction.
  94.             }
  95.             colours[colour].push_back(r);   //The list will be created if it doesn't exist. That's how a map works.
  96.         }
  97.         //This would have required the use of equal_range, if a multimap had been chosen.
  98.         bool anyWritten=false;
  99.         for (map<int,list<Rectangle> >::const_iterator it=colours.begin();it!=colours.end();++it)   {
  100.             int area=0;
  101.             for (list<Rectangle>::const_iterator lIt=it->second.begin();lIt!=it->second.end();++lIt) area+=lIt->area();
  102.             if (area>0) {
  103.                 if (anyWritten) cout<<' ';
  104.                 cout<<it->first<<' '<<area;
  105.                 anyWritten++;
  106.             }
  107.         }
  108.         cout<<endl;
  109.     }   while (!cin.eof());
  110.     return 0;
  111. }
RAW Paste Data