rachit_jain's blog

Area of union of rectangles whose base is on x axis
By rachit_jain, history, 8 years ago, In English

Let S be a set of n axis-parallel rectangles in the plane, so that the bottom edge of each rectangle in S lies on the x-axis.Find the area of the union of rectangles I am stuck on this problem ,from net I learnt it uses some sweep line algo but how do I implement it

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Consider the set of "events" E, with 2n elements. Each event is the beginning or the end of a rectangle, and it knows the height of the rectangle it corresponds to. Maintain a multiset of active rectangles, and process the events in order of x-coordinate (you can sort them at the beginning): for events corresponding to the beginning of a rectangle, you put the height of the rectangle in your multiset; for events corresponding to the end of a rectangle, you remove one instance of the height from your multiset.

Before you process event i (i >= 2), take the largest element in the multiset (call it Y), and add (X[i] — X[i-1]) * Y to your answer. (X[i] is the X coordinate of the ith event.)

The time complexity is .

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Ya I understood your algorithm, Thank you very much for your detailed explaination

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have coded the solution in C using heap instead of a multiset as multiset is not in c, I am having some problem as when I encounter the end of a rectangle I want to delete the height of that rectangle which I inserted in beginning which takes O(n) time ..How to make it to O(logn) time

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      You can store the position of each element in the heap so that when you want to delete a height, you know what position you must delete. You then adjust the rest of the heap accordingly. But why do all that when you can simply use C++ and do it all with just a couple of lines?

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is the C++ implementation for this problem.

It calculates perimeter of union of the given rectangles too, also it supports double values.

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Dear rachit jain, Codeforces has a strict no duplicate account policy which u seem to have violated with ur handles machau and bakwas :p Anyway on a more serious note, begging for assignment solutions here is not appreciated.You may expect action to be taken. But until then enjoy felicity. — DS TAs

→ Reply