SHARE
TWEET

Tuenti Contest 15 (Pablo Moreno)

Nbrevu Jun 20th, 2011 896 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top