nownikhil's blog

Interesting Line Sweep Problem
By nownikhil, 11 years ago, In English

Hi all,

I was trying to solve this problem on spoj. http://www.spoj.com/problems/WILD/

If we treat each evil candidate as a point and consider the cube (0,0,0) — (x,y,z). The problem is reduced to finding the volume of union of cubes. The answer in this case will be m^3 — volume.

The complexity is turning out to be n*n*log(n). Can anyone suggest a better algorithm?

Thanks

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can do it in O(n * log2(n)) in the same way you find the area of the union of rectangles in O(n * log(n)), by using segment trees, and in each leaf, another segment tree...

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

    Can you explain a little more about the implementation? Or if you can post a pseudo code for the same.

    → Reply