10613 - Mushroom Misery

Moderator: Board moderators

pminkov
New poster
Posts: 8
Joined: Wed Oct 17, 2001 2:00 am
Location: Bulgaria, Sofia

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

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
Just this:

Input:
1
1 1
0 0 40

Output:
1

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:
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+(4-2*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
I used divide and conquer to solve this problem.

marian
New poster
Posts: 30
Joined: Sun Oct 27, 2002 4:01 pm
Contact:
OK, now I'm ashamed. It's sort of school algorithm I got accepted. Thank you very much for your hint.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
Hmph, I used a (kind of) plane sweeping to get this problem accepted.
What divide&conquer techniques could be used on this problem?!
JongMan @ Yonsei

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:
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 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).
I've got AC.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
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).
Sorry, I have one question.
How to cover the circles with some proper rectangles?
Any bettor method?

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico
I think it's possible to make the circles just as 2 rectangles (like making a cross) and then solve with NlogN.
Miguel & Marina

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
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.
I thought it is possible.
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(x-r),ceil(y+r),ceil(x+r),floor(y-r)) 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

Miguel Angel
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

fennec
New poster
Posts: 4
Joined: Thu Jul 29, 2004 12:18 pm

WAing...

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

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Re: WAing...

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
Maybe it needs more rectangle to represent a circle.

fennec
New poster
Posts: 4
Joined: Thu Jul 29, 2004 12:18 pm

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:)

Margarita
New poster
Posts: 8
Joined: Mon Jan 23, 2006 7:28 pm
Location: Ukraine, Kharkiv
Contact:
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).
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 :'(