heavenly_'s blog

By heavenly_, history, 2 weeks ago, In English

Hello, I'm doing this problem, the statement is in Vietnamese, therefore I'll give you a summary:

Given n rectangles on a 2D coordination (x, y, w, h), two rectangles are connected if any of it's edges touches, find the largest connected rectangles area (w, h <= 500), no rectangles overlaps with each other and each rectangle is (x, y, x + w, y + h)

The editorial suggested using DSU combined with sweep line, however I'm still not clear on it, I'd appreciate some help, thanks!

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Using DSU you can find which rectangles form a connected component(some of their edges touch). Notice that your problem now becomes: Find the biggest area of the union of rectangles of some component. Solve for each component separately and take the biggest value. To solve for the area of union you can use a sweep line and a segment tree with propagation as mentioned here(blog).

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why can't we simply add areas when uniting sets?

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      well, since no two rectangles overlap each other, you can actually do that. i think segtree only necessary if rectangles can overlap each other.

»
2 weeks ago, # |
Rev. 3   Vote: I like it +14 Vote: I do not like it

I think the easier way is to just use coordinate compression and then DFS on a grid to find the largest area. However, this works only if the number of rectangles are $$$n \leq 1000$$$, as this algorithm costs $$$O(n^2)$$$ in time complexity and memory complexity. Here's how.

Assume $$$x,y$$$ could be arbitrarily large (let's say like $$$-10^9 \leq x,y \leq 10^9$$$, I'm not gonna set the bounds larger than this due to how much a long long can contain). Notice that we only need to keep track of at most $$$2n$$$ distinct x-coordinates, which are the values of $$$x$$$ and $$$x+w$$$ for each rectangle. Similar thing can be said for $$$2n$$$ distinct y-coordinates, but with values $$$y$$$ and $$$y+h$$$ instead. And now, if we draw a line that corresponds to these coordinates, we have this new "grid" where it only consists of $$$2n$$$ horizontal and vertical lines each. Funnily enough, each "tile" in this new "grid" is either completely covered or not covered at all (remember this sentence as point 1).

For this next steps, there are many ways to do it, but I'm gonna explain mine. Let's treat this new "grid" as just yet another number grid (let's call it $$$A$$$) with the size of $$$(2n-1) \times (2n-1)$$$ (since there are $$$2n$$$ lines horizontally and vertically), where each tile have a value. In this case, the value for each tile corresponds to the area between the same $$$4$$$ lines that border said tile in the original cartesian grid. For example, if in $$$A$$$, the lines that border the tile are $$$x = 6, x = 9, y = 4, y = 20$$$, then the value of that tile is the area of the rectangle formed by those lines in the original cartesian grid, which is $$$(9-6) \times (20-4) = 48$$$. Notice that we now have successfully compressed a very large cartesian grid into a small $$$(2n-1) \times (2n-1)$$$ square grid $$$A$$$, and it can be easily proven that the construction of $$$A$$$ can be done in $$$O(n^2)$$$ time. But, what do we do next?

Notice that from point 1, we can see that each tile in $$$A$$$ is either fully covered, or not covered at all. Now, if we assume that each tile covered by a rectangle as a tile filled with land, and other tiles as sea, then this problem is basically reduced to maximum area from all islands in the grid $$$A$$$, where an island is just connected lands. Except, each tile has custom value, which the problem is probably more like "maximum value from all islands in the grid $$$A$$$" or smth. This problem can easily be solved using DFS (or DSU but why lmao it's slower), and since the size of $$$A$$$ is $$$(2n-1) \times (2n-1)$$$, we essentially solve the whole problem in $$$O((2n-1)^2) = O(n^2)$$$ time.

Fun fact: with this technique, you can solve even for $$$0 \leq h,w \leq 10^9$$$ (dw all values can fit into long long lmao). also, no need to worry about overlapping rectangles (though, you may have to use like a sweep line + segtree to achieve $$$O(n^2 \log n)$$$ time).

Edit 1: pls let me know if something is incorrect here, as i'm writing this while half hungry .w.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks everyone, I've managed to solve the problem, if anyone's curious, here's how:

O(N * 2 * (w + h) * log(4 * N)) solution: use a map to store the 4 edges of each rectangles, then iterate through all the rectangles and connect them by iterating from (x, x + w) and (y, y + w) and using DSU.

O(2 * log(2 * N)^2 * N) solution: use two separate maps, one to store the horizontal side, another to store the vertical side, you can then sweep line and keep uniting the rectangles through the horizontal/vertical coordinates after sorting it