Area Covered by Rubber Band Around a Collection of Circles

Правка en1, от 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!

Теги computational geometry, convex hull

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский vamaddur 2017-08-14 17:21:18 1010 Initial revision (published)