fork(1) download
copy 
  1. /**
  2. * Rectangle union
  3. * Input: N (number of rectangles), and then N rectangles (x1 y1 x2 y2)
  4. * Output: area of union of all rectangles
  5. * 
  6. * Author: Erel Segal
  7. * Created: 2010-10-07
  8. *
  9. * TODO: Use an Interval Tree: http://e...content-available-to-author-only...a.org/wiki/Interval_tree 
  10. *   to make RectangleCollection::contains() more efficient.
  11. */
  12.  
  13. #include <iostream>
  14. #include <algorithm>
  15. #include <set>
  16. #include <vector>
  17. #include <time.h>
  18. #include <assert.h>
  19. using namespace std;
  20.  
  21. typedef unsigned long long ulonglong;
  22.  
  23.  
  24.  
  25. template <class Iterator> void print (ostream& out, Iterator iFrom, Iterator iTo) {
  26.         for (; iFrom<iTo; ++iFrom) {
  27.                 out << *iFrom << " ";
  28.         }
  29.         out << endl;
  30. }
  31.  
  32.  
  33. template <class Iterator> void shuffle (Iterator iFrom, Iterator iTo) {
  34. 	int size = iTo-iFrom;
  35. 	for (int i=1; i<size; ++i) {
  36. 		Iterator iCurrent = iFrom+i;
  37. 		Iterator iNew = iFrom+(rand()%(i+1));
  38. 		swap(*iCurrent, *iNew);
  39. 	}
  40. }
  41.  
  42. template <class T> void unique_vector (vector<T>& v) {
  43. 	typename vector<T>::iterator new_end = ::unique (v.begin(), v.end());
  44. 	v.resize(new_end-v.begin());
  45. }
  46.  
  47.  
  48. struct Rectangle {
  49.         int x1, y1, x2, y2;
  50.         Rectangle() {}
  51.         Rectangle(int _x1, int _y1, int _x2, int _y2) { x1=_x1; x2=_x2; y1=_y1; y2=_y2; }
  52.         friend istream& operator>> (istream& in, Rectangle& r) { in >> r.x1 >> r.y1 >> r.x2 >> r.y2; return in; }
  53.         friend ostream& operator<< (ostream& out, const Rectangle& r) { out << r.x1 << " " << r.y1 << " " << r.x2 << " " << r.y2; return out; }
  54.         friend ostream& operator<< (ostream& out, const Rectangle* r) { return (out << *r); }
  55.  
  56.         int midx() const { return (x1+x2)/2; }
  57.         int midy() const { return (y1+y2)/2; }
  58.  
  59.         bool contains(int x, int y) const { return x1<=x && x<x2 && y1<=y && y<y2; }
  60.         bool containsX (int x) const { return x1<=x && x<x2; }
  61.         bool containsY (int y) const { return y1<=y && y<y2; }
  62.  
  63.         bool entirelyLefter(int x) const { return x2<=x; }
  64.         bool entirelyRighter(int x) const { return x<x1; }
  65. };
  66.  
  67.  
  68. bool lefter(const Rectangle* A, const Rectangle* B) {
  69.         return A->x1 < B->x1;
  70. }
  71.  
  72. bool righter(const Rectangle* A, const Rectangle* B) {
  73.         return A->x2 > B->x2;
  74. }
  75.  
  76. typedef vector<Rectangle*> PRectangleVector; 
  77. /**
  78.  An interval tree for sorting Rectangles by their x value
  79.  @see: http://e...content-available-to-author-only...a.org/wiki/Interval_tree
  80.  */
  81. class RectangleTree {
  82.         int myThreshold;
  83.         RectangleTree* lefterRectangles;
  84.         RectangleTree* righterRectangles;
  85.         PRectangleVector containingRectanglesSortedByLeft;
  86.         PRectangleVector containingRectanglesSortedByRight;
  87.  
  88.         // INVARIANT 1: a tree-node has children if and only if it has rectangles.
  89.         //   (when we create a tree, we first insert a rectangle, only then we create children).
  90.  
  91. public:
  92.         RectangleTree(): lefterRectangles(NULL), righterRectangles(NULL), containingRectanglesSortedByLeft(), containingRectanglesSortedByRight() {}
  93.  
  94.         bool isEmpty() const { return containingRectanglesSortedByLeft.empty(); }
  95.  
  96.         void insert (Rectangle* newRectangle) {
  97.                 //cout << "insert " << newRectangle << "(size=" << containingRectanglesSortedByLeft.size() << ")" << endl;
  98.                 if (isEmpty()) {
  99.                         //cout << "insert to empty" << endl;
  100.                         myThreshold = newRectangle->midx();
  101.                         containingRectanglesSortedByLeft.push_back(newRectangle);
  102.                         containingRectanglesSortedByRight.push_back(newRectangle);
  103.                 } else if (newRectangle->containsX(myThreshold)) {
  104.                         //cout << "insert to containing" << endl;
  105.                         containingRectanglesSortedByLeft.push_back(newRectangle);
  106.                         containingRectanglesSortedByRight.push_back(newRectangle);
  107.                 } else if (newRectangle->entirelyLefter(myThreshold)) {
  108.                         //cout << "insert to left" << endl;
  109.                         if (!lefterRectangles)
  110.                                 lefterRectangles = new RectangleTree();
  111.                         lefterRectangles->insert(newRectangle);
  112.                 } else if (newRectangle->entirelyRighter(myThreshold)) {
  113.                         //cout << "insert to right" << endl;
  114.                         if (!righterRectangles)
  115.                                 righterRectangles = new RectangleTree();
  116.                         righterRectangles->insert(newRectangle);
  117.                 } else {
  118.                         throw string("Impossible case");
  119.                 }
  120.         }
  121.  
  122.         void sort() {
  123.                 std::sort(containingRectanglesSortedByLeft.begin(), containingRectanglesSortedByLeft.end(), &lefter);
  124.                 std::sort(containingRectanglesSortedByRight.begin(), containingRectanglesSortedByRight.end(), &righter);
  125.                 if (lefterRectangles) lefterRectangles->sort();
  126.                 if (righterRectangles) righterRectangles->sort();
  127.         }
  128.  
  129.         bool contains(int x, int y) const {
  130.                 bool result = false;
  131.                 if (isEmpty()) { 
  132.                         result = false;  // no rectangles -> no children (by invariant 1)
  133.                 } else if (x<myThreshold) {
  134.                         // search for containing rectangles that start lefter than x
  135.                         for (PRectangleVector::const_iterator it=containingRectanglesSortedByLeft.begin(); it!=containingRectanglesSortedByLeft.end(); ++it) {
  136.                                 const Rectangle& rect = **it;
  137.                                 if (rect.contains(x,y)) 
  138.                                         result = true;
  139.                                 if (rect.entirelyRighter(x))
  140.                                         break; // since the rectangles are sorted
  141.                         }
  142.                         if (!result)
  143.                         // search for lefter rectangles that start lefter than x
  144.                                 result = (lefterRectangles? lefterRectangles->contains(x,y): false);
  145.                 } else {// (x>=myThreshold) 
  146.                         // search for containing rectangles that end righter than x
  147.                         for (PRectangleVector::const_iterator it=containingRectanglesSortedByRight.begin(); it!=containingRectanglesSortedByRight.end(); ++it) {
  148.                                 const Rectangle& rect = **it;
  149.                                 if (rect.contains(x,y)) 
  150.                                         result = true;
  151.                                 if (rect.entirelyLefter(x))
  152.                                         break; // since the rectangles are sorted
  153.                         }
  154.                         // search for righter rectangles that start righter than x
  155.                         if (!result)
  156.                                 result = (righterRectangles? righterRectangles->contains(x,y): false);
  157.                 }
  158.                 //cout << "contains("<< x << "," << y << ")=" << result << endl;
  159.                 return result;
  160.         }
  161.  
  162.         void print(ostream& out, string prefix="") const {
  163.                 out << prefix << "LEFTER THAN " << myThreshold << ":" << endl;
  164.                 if (lefterRectangles) lefterRectangles->print(out, prefix+"  ");
  165.                 out << prefix << "CONTAINING " << myThreshold << " SORTED BY LEFT: " << endl;
  166.                 out << prefix; ::print(out, containingRectanglesSortedByLeft.begin(), containingRectanglesSortedByLeft.end());
  167.                 out << prefix << "CONTAINING " << myThreshold << " SORTED BY RIGHT: " << endl;
  168.                 out << prefix; ::print(out, containingRectanglesSortedByRight.begin(), containingRectanglesSortedByRight.end());
  169.                 out << prefix << "RIGHTER THAN " << myThreshold << ":" << endl;
  170.                 if (righterRectangles) righterRectangles->print(out, prefix+"  ");
  171.         }
  172.  
  173. };
  174.  
  175. class RectangleCollection {
  176.         vector<Rectangle> myRectangles;
  177.         RectangleTree myRectangleTree;
  178.  
  179.         vector<int> xs; // a sorted array of all x coordinates.
  180.         vector<int> ys; // a sorted array of all y coordinates.
  181.  
  182.         int myCount;
  183.         bool isSorted;
  184.  
  185. public:
  186.         RectangleCollection(int newCount): 
  187.                 myRectangles(newCount), 
  188.                 myRectangleTree(),
  189.                 xs(2*newCount), ys(2*newCount), myCount(0), isSorted(false) {}
  190.  
  191.         void add(const Rectangle& rect) {
  192.                 //cout << "add " << rect << endl;
  193.                 assert(!isSorted);
  194.                 myRectangles[myCount] = rect;
  195.  
  196.                 xs[2*myCount] = rect.x1;
  197.                 xs[2*myCount+1] = rect.x2;
  198.                 ys[2*myCount] = rect.y1;
  199.                 ys[2*myCount+1] = rect.y2;
  200.  
  201.                 ++myCount;
  202.         }
  203.  
  204.         void sort() {
  205.                 //cout << "xs: "; ::print (cout, xs.begin(), xs.end());
  206.                 //cout << "ys: "; ::print (cout, ys.begin(), ys.end());
  207.                 ::sort (xs.begin(), xs.end());
  208.                 ::sort (ys.begin(), ys.end());
  209.                 //cout << "xs: "; ::print (cout, xs.begin(), xs.end());
  210.                 //cout << "ys: "; ::print (cout, ys.begin(), ys.end());
  211.                 ::unique_vector (xs);
  212.                 ::unique_vector (ys);
  213.                 //cout << "xs: "; ::print (cout, xs.begin(), xs.end());
  214.                 //cout << "ys: "; ::print (cout, ys.begin(), ys.end());
  215.                 //exit(1);
  216.                 shuffle(myRectangles.begin(), myRectangles.end());
  217.                 for (size_t i=0; i<myRectangles.size(); ++i) {
  218.                         myRectangleTree.insert(&myRectangles[i]);
  219.                 }
  220.                 myRectangleTree.sort();
  221.  
  222.                 //myRectangleTree.print(cout); cout << "sort end!" << endl;
  223.  
  224.                 isSorted=true;
  225.         }
  226.  
  227.         bool contains (int x, int y) const {
  228.                 return myRectangleTree.contains(x,y);
  229.  
  230.                 for (vector<Rectangle>::const_iterator i=myRectangles.begin(); i<myRectangles.end(); ++i) {
  231.                         if (i->contains(x,y))
  232.                                 return true;
  233.                 }
  234.                 return false;
  235.         }
  236.  
  237.         // calculate the total area
  238.         ulonglong area() const {
  239.                 assert(isSorted);
  240.                 ulonglong a = 0;
  241.                 for (int x=0; x<xs.size()-1; ++x) {
  242.                         for (int y=0; y<ys.size()-1; ++y) {
  243.                                 if (this->contains(xs[x],ys[y])) {
  244.                                         int pixelArea = (xs[x+1]-xs[x]) * (ys[y+1]-ys[y]);
  245.                                         a += pixelArea;
  246.                                 }
  247.                         }
  248.                 }
  249.                 return a;
  250.         }
  251.  
  252.         void assertArea(ulonglong expected) const {
  253.                 time_t before = time(NULL);
  254.  
  255.                 size_t a = area();
  256.                 if (a!=expected) {
  257.                         cerr << "ERROR: Area should be " << expected << " but was " << a << endl;
  258.                 } else {
  259.                         time_t after = time(NULL);
  260.                         cout << "calculated area of " << myCount << " rects in " << (after-before) << " seconds" << endl;
  261.                 }
  262.         }
  263.  
  264. };  // RectangleCollection
  265.  
  266.  
  267.  
  268. void testDiagonal0(int N) {
  269.         RectangleCollection rects(N);
  270.  
  271.         for (int i=0; i<N; ++i) {
  272.                 rects.add(Rectangle(2*i,2*i,2*i+1,2*i+1));
  273.         }
  274.         rects.sort();
  275.         rects.assertArea(N);
  276. }
  277.  
  278.  
  279. void testDiagonal1(int N) {
  280.         RectangleCollection rects(N);
  281.  
  282.         for (int i=0; i<N; ++i) {
  283.                 rects.add(Rectangle(i,i,i+1,i+1));
  284.         }
  285.         rects.sort();
  286.         rects.assertArea(N);
  287. }
  288.  
  289. void testDiagonal2(int N) {
  290.         RectangleCollection rects(N);
  291.         for (int i=0; i<N; ++i) {
  292.                 rects.add(Rectangle(i,i,i+2,i+2));
  293.         }
  294.         rects.sort();
  295.         rects.assertArea(4*N-(N-1));
  296. }
  297.  
  298. void testEqual(int N) {
  299.         RectangleCollection rects(N);
  300.         for (int i=0; i<N; ++i) {
  301.                 rects.add(Rectangle(0,0,1,1));
  302.         }
  303.         rects.sort();
  304.         rects.assertArea(1);
  305. }
  306.  
  307. int main() {
  308.         int N; // number of rectangles in input
  309.         cin >> N;
  310. /*
  311.         time_t before = time(NULL);
  312.         testDiagonal0(N);
  313.         testDiagonal1(N);
  314.         testDiagonal2(N);
  315.         testEqual(N);
  316.         time_t after = time(NULL);
  317.         cout << "calculated areas of " << N << " rects in " << (after-before) << " seconds" << endl;
  318.         exit(1);
  319. */
  320.         RectangleCollection rects(N);
  321.         Rectangle rect;
  322.         for (int i=0; i<N; ++i) {
  323.                 cin >> rect;  // input
  324.                 rects.add(rect);
  325.         }
  326.         rects.sort();
  327.  
  328.         cout << rects.area() << endl;
  329. }
  330.  
stdin
copy 
2
10 10 20 20
15 15 25 30
compilation info 
prog.cpp: In member function ‘ulonglong RectangleCollection::area() const’:
prog.cpp:241: warning: comparison between signed and unsigned integer expressions
prog.cpp:242: warning: comparison between signed and unsigned integer expressions
stdout
copy 
225
https://ideone.com/MpLqp
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!