Nbrevu

Tuenti Contest 15 (Pablo Moreno)

Jun 20th, 2011
1,165
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

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×