Help With USACO Problem
Moderator: Board moderators
Help With USACO Problem
Hello . I want to ask you for some idea for one usaco problem. It is called Shaping Regions. It is a Chapter 2 problem. If you can give some idea please do it . Thank you very much . ( I am a newbie in the forum and my english is not so good  sorry ! )

 New poster
 Posts: 4
 Joined: Thu Jul 08, 2004 3:13 pm

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
MLE  memory limit exceeded
TLE  time limit exceeded
RTE  runtime error (crash)
Best regards
DM
TLE  time limit exceeded
RTE  runtime error (crash)
Best regards
DM
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)
My algorithm works something like that:
I sort rectangles' edges ('opening' and 'closing' edges) by xcoordinate. Then I start to sweep from left to right  for every event (edge parallel to y axis) I count the area (and also the colors) of rectangles which intersect or cover this event and next event (some of them may not intersect next event). The problem is to calculate that area between two events, you have to use some kind of interval tree or structure which give you possibilty to add new interval in O(log n) time. 'Interval' is the height of rectangle and its y coordinates.
If one rectangle is 'higher' (abstract  contains the problem statement) than another then you have to erase all intervals its intersect from your structure. After you have added all the intervals you only need to count the colors. Thus running all that costs you O (n^2*log n) time  n*2 events * n*log n interval addings.
Maybe it'll help.
Cheers,
yaro
I sort rectangles' edges ('opening' and 'closing' edges) by xcoordinate. Then I start to sweep from left to right  for every event (edge parallel to y axis) I count the area (and also the colors) of rectangles which intersect or cover this event and next event (some of them may not intersect next event). The problem is to calculate that area between two events, you have to use some kind of interval tree or structure which give you possibilty to add new interval in O(log n) time. 'Interval' is the height of rectangle and its y coordinates.
If one rectangle is 'higher' (abstract  contains the problem statement) than another then you have to erase all intervals its intersect from your structure. After you have added all the intervals you only need to count the colors. Thus running all that costs you O (n^2*log n) time  n*2 events * n*log n interval addings.
Maybe it'll help.
Cheers,
yaro
Easier algorithm
yaro's algorithm works in n^2lgn, but there is an algorithm that is easier to code which works in n^3 (which is still good enough for the test cases). basically note that everytime you put a new rectangle on top, it intersects each rectangle to make at most 4 new rectangles. so just loop through adding each rectangle and checking which of the 4 u can make for each intersection.