Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

largest connected rectangle area?

Revision en1, by heavenly_, 2024-04-02 12:16:11

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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English heavenly_ 2024-04-02 12:16:11 518 Initial revision (published)