Блог пользователя rachit_jain

Area of union of rectangles whose base is on x axis
Автор rachit_jain, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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 .

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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?

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Here is the C++ implementation for this problem.

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

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить