Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

mathforces's blog

By mathforces, history, 3 years ago, In English,

I tried to think of many different approaches to this problem but still can't figure out. Can you guys give me a hint? Thank you so much.

Problem VCIRCLES: http://www.spoj.com/problems/VCIRCLES/

Give N circles. Calculate the total area that these N circles cover. The i-th circle has coordinate of center (Xi, Yi) and radius Ri.

1 ≤ N ≤ 50. -10000 ≤ Yi-Ri, Yi + Ri, Xi-Ri, Xi + Ri ≤ 10000

 
 
 
 
  • Vote: I like it
  • +27
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Illusi0nary (previous revision, new revision, compare).

»
3 years ago, # |
  Vote: I like it +28 Vote: I do not like it

The "fair" way of solving this problem would be the following: calculate all possible intersection points between pairs of circles, take their x coordinates. Add to that also the leftmost and rightmost x coordinate for each circle, and sort all of those. Then, for each two subsequent x's, x 1 and x 2, we want to know what is the area of the vertical stripe between x 1 and x 2 that the circles cover. Each circle cuts out some "circle slice" (the shape you get if you intersect a circle with a vertical stripe). Note that between x 1 and x 2 no circles intersect, so if you look at the opening and closing arc for each slice, they will form some sort of a bracket sequence. Generally you will end up needing to compute the area enclosed by two vertical lines and two arcs, which can be derived mathematically.

The "cheaty" way of solving similar problems is this: take the bounding box of all circles. Then you can recursively divide the box into four smaller ones, each of those divide even further, etc. At each moment in this recursion you check for three things: if your box is fully contained in some circle, you add the area of the box to the answer and stop. If no circle intersects the box, it doesn't contribute any area, stop. If the box is very small, also stop. But I have no idea whatsoever how to know if this will work or not other than just trying :)

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thank you so much for your approach! I didn't think about the bracket sequence, such an amazing way.

    Also I found someone code: https://ideone.com/w1j1o3. I'm not sure what exaclty the code did. Can you have a look? Thanks again!