Area Covered by Rubber Band Around a Collection of Circles

Revision en1, by vamaddur, 2017-08-14 17:21:18

Pictures of the Problem

The gist of the problem is to find the area that a rubber band around N circles of equal radius encloses. My thought process is as follows:

1) Find the convex hull of all the circle centers.

2) Use the Shoelace Theorem to find the area of the convex hull.

3) Add the area of the convex hull and the area of one circle of radius K to a running total.

4) Add the area of augmenting rectangles on the convex hull to the running total; for each rectangle, the area is found by multiplying the distance between two adjacent vertices on the hull by K (essentially the hull perimeter times K)

My implementation of these ideas is here, which gets WA on all hidden cases. Is my logic incorrect, or is there a bug in my implementation?

Please help, and thanks in advance!

Tags computational geometry, convex hull

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English vamaddur 2017-08-14 17:21:18 1010 Initial revision (published)