10613 - Mushroom Misery

[pminkov]

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]

Just this:

Input:
1
1 1
0 0 40

Output:
1

[marian]

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

[Adrian Kuegel]

I used divide and conquer to solve this problem.

[marian]

OK, now I'm ashamed. It's sort of school algorithm I got accepted. Thank you very much for your hint.

[Whinii F.]

Hmph, I used a (kind of) plane sweeping to get this problem accepted.
What divide&conquer techniques could be used on this problem?!

[rotoZOOM]

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.
Thanks Adrian.

[windows2k]

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?
Please give some hints, thx

[Miguel Angel]

I think it's possible to make the circles just as 2 rectangles (like making a cross) and then solve with NlogN.

[windows2k]

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]

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

[fennec]

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]

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]

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]

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 :'(