Hi everyone!
I'm not managing to get AC in this one... It seems fairly easy though. My program handles correctly the sample input, the problems stated in the fix page of the problem and some other cases. Among these I included some samples with overlapping sides and points of the squares...
I can't remember anything else...
If anyone knows of something, please help! Thanks!
688 - Mobile Phone Coverage
Moderator: Board moderators
The best method to solve this probelm is to transform the given rectangles into many stripes.
First sort by x coordinates and sort the smaller rectangles(for every consecutive x interval) considering y coordinate. Add them up and you get the required answer.
This statement might seem very confusing but read it carefully and you will get the theme of it.
First sort by x coordinates and sort the smaller rectangles(for every consecutive x interval) considering y coordinate. Add them up and you get the required answer.
This statement might seem very confusing but read it carefully and you will get the theme of it.
There's at least 2 ways I can think of to solve it. The easy way is to normalize the coordinates and just count the sum of area of rectangles that has at least one square covering it. The other way, which works for input size at much as 500000 is to use the sweep line algorithm for finding area of unions of orthogonal rectangles. Just look it up in any computational geometry textbook.