help with one "usaco hard problem" ... please.....

anupam · Post by **anupam** » Fri Jul 02, 2004 7:55 pm

Please help me in the following problem. I have applied two different alg. but one got mle and the other got tle. Please rescue me from the 'LE' s.

Here is the problem.. from USACO

Shaping Regions
N opaque rectangles (1 <= N <= 1000) of various colors are placed on a white sheet of paper whose size is A wide by B long. The rectangles are put with their sides parallel to the sheet's borders. All rectangles fall within the borders of the sheet so that different figures of different colors will be seen.

The coordinate system has its origin (0,0) at the sheet's lower left corner with axes parallel to the sheet's borders.

PROGRAM NAME: rect1
INPUT FORMAT
The order of the input lines dictates the order of laying down the rectangles. The first input line is a rectangle "on the bottom". Line 1: A, B, and N, space separated (1 <= A,B <= 10,000)
Lines 2-N+1: Five integers: llx, lly, urx, ury, color: the lower left coordinates and upper right coordinates of the rectangle whose color is `color' (1 <= color <= 2500) to be placed on the white sheet. The color 1 is the same color of white as the sheet upon which the rectangles are placed.

SAMPLE INPUT (file rect1.in)
20 20 3
2 2 18 18 2
0 8 19 19 3
8 0 10 19 4

OUTPUT FORMAT
The output file should contain a list of all the colors that can be seen along with the total area of each color that can be seen (even if the regions of color are disjoint), ordered by increasing color. Do not display colors with no area.
SAMPLE OUTPUT (file rect1.out)
1 91
2 84
3 187
4 38

Please help. Drowning....

Cosmin.ro · Post by **Cosmin.ro** » Sat Jul 03, 2004 12:24 am

I got accepted using the following solution:

I normalized the coordinates to go from 0 to 2000 (becose there are at most 2000 different x coordinates and 2000 y coordinates), then I used a matix of 2000*2000 cells to mark the colors of the rectangles, i guess this worked becose the tests are weak.

You can get a O(n^2 log n) solution by solving the one dimension problem in O(n log n) using a heap or a interval tree.

anupam · Post by **anupam** » Sat Jul 03, 2004 8:20 am

how to normalize the coordinates?
Anupam

Cosmin.ro · Post by **Cosmin.ro** » Mon Jul 05, 2004 4:16 pm

Sort them!

nibbler · Post by **nibbler** » Thu Jul 22, 2004 8:04 pm

i used the following aproach: if two rectangles overlap, then what is left of the bottom rectlangle can be remembered as few new rectangles. i implemented it using linked list and got a very fast solution.