vamaddur's blog

Area Covered by Rubber Band Around a Collection of Circles
By vamaddur, history, 7 years ago, In English

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!

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

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

This could be a problem of precision. Since the coordinate points are integers, you could try to find the convex hull without moving to doubles. The same can be said of the area of the convex hull (except for multiplying by 0.5 at the end).

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    That could be a problem @mathusalen, buy what about the actual correctness of the algorithm I am applying?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Seems legit to me. You could try any other convex hull algorithm as in: https://github.com/jaehyunp/stanfordacm/blob/master/code/ConvexHull.cc to check that this part is OK. By curiosity where this problem comes from?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        @mathusalen, it comes from a website called "DoSelect". Unfortunately, the website does not support upsolving (the contest just ended), and their management is refusing to release the test data to me since it is "too hard".

        I'm probably not going to do contests on there again, but I still would like to find a countercase to my code.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          There is a huge possibility their test cases are wrong. I've never participated in any contest with all test cases correct on DoSelect. They randomly update test cases whenever they want and rejudge solutions even if some contestant has locked his submissions.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            ← Rev. 3   Vote: I like it 0 Vote: I do not like it

            @TooDumbToWin I actually messaged their group on Facebook, and they kept insisting that my logic was incorrect during the contest. I gave them the benefit of the doubt by posting here to see if anyone in a legit community could debug my code, if it had errors. In addition, they refuse to release the test cases or a working solution to me.

            → Reply