10613  Mushroom Misery
Moderator: Board moderators
10613  Mushroom Misery
Can anyone please give me some test cases for this problem,
I keep getting WA, although I think I handle all special cases.
Petko Minkov
I keep getting WA, although I think I handle all special cases.
Petko Minkov
Hello,
I have totally stucked with this problem. The only solution I could think of, is to cover the circles with rectangles, and then solve simpler problem with rectangles in O(N log N) (N is number of rectangles).
We can trivially cover one circle with 2*r rectangles (r is circle radius) , horizontal or vertical stripes, but that's too much (r can be 1000000). It's not difficult to cover circle with something like 1+(42*sqrt(2))*r rectangles (just inscribe largest possible square, and cover the rest with stripes) But that seems still to much.
Could somebody give me some hint? Thank you.
Marian
I have totally stucked with this problem. The only solution I could think of, is to cover the circles with rectangles, and then solve simpler problem with rectangles in O(N log N) (N is number of rectangles).
We can trivially cover one circle with 2*r rectangles (r is circle radius) , horizontal or vertical stripes, but that's too much (r can be 1000000). It's not difficult to cover circle with something like 1+(42*sqrt(2))*r rectangles (just inscribe largest possible square, and cover the rest with stripes) But that seems still to much.
Could somebody give me some hint? Thank you.
Marian

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 Learning poster
 Posts: 63
 Joined: Mon Dec 22, 2003 5:05 am
 Location: Russia, Chelyabinsk
 Contact:
You just divide ALL area onto parts and parts onto smaller parts and so on.Whinii F. wrote:Hmph, I used a (kind of) plane sweeping to get this problem accepted.
What divide&conquer techniques could be used on this problem?!
You should stop when size of area is 1 square meter or when no one circle intersect your area.
All you need on each step you should check all circles.
I check if area completely covered by some circle as well (for speed purposes).
I've got AC.
Thanks Adrian.
Sorry, I have one question.marian wrote: I have totally stucked with this problem. The only solution I could think of, is to cover the circles with rectangles, and then solve simpler problem with rectangles in O(N log N) (N is number of rectangles).
How to cover the circles with some proper rectangles?
Any bettor method?
Please give some hints, thx

 Learning poster
 Posts: 60
 Joined: Tue Aug 13, 2002 2:39 am
 Location: Mexico
I thought it is possible.Miguel Angel wrote:I think it's possible to make the circles just as 2 rectangles (like making a cross) and then solve with NlogN.
But how to find the two rectangles.
First I can find an big rectangle to cover the circle.
Let rectangle represent as (left,up,right,down)
I could find a rectange (floor(xr),ceil(y+r),ceil(x+r),floor(yr)) to cover the circle.
But the four corners maybe not used.
Many special cases should be considered.
Would someone give better method to represent the circle? Thx

 Learning poster
 Posts: 60
 Joined: Tue Aug 13, 2002 2:39 am
 Location: Mexico
Yeap, well if you think it as a big square first, is hard for sure..But you may agree the following, in the big square you can fit two rectangles of with w and height h, making a cross and covering the whole circle. If don't believe me, let's suppose it exist, if exist those 2 rectangles cross in 4 points..each point is at 45
Miguel & Marina
Re: WAing...
Maybe it needs more rectangle to represent a circle.fennec wrote:I change each circle to two rectangles, and use O(n*log(n)) to solve it, but I got wa , Could some one give me some special Input&Output?
TKS
ths,I will try
But just in my alg, I first found the 45 degree points, and use floor and ceil to deal with them separately, so can you give me an example to show my fault , Tks:)
I used the same method but & got TLE. I divide all area in 4 parts, check if this part is covered by circle or, on the contrary, if it's not intersected and does not contains circle. i thought i made all optinizations but still got TLE :'(rotoZOOM wrote: You just divide ALL area onto parts and parts onto smaller parts and so on.
You should stop when size of area is 1 square meter or when no one circle intersect your area.
All you need on each step you should check all circles.
I check if area completely covered by some circle as well (for speed purposes).