mathforces's blog

By mathforces, history, 7 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

| Write comment?
»
7 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, x1 and x2, we want to know what is the area of the vertical stripe between x1 and x2 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 x1 and x2 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 :)