Abinash's blog

Ternary Search Geometry Problem UVa 11829 — L’s in a Circle
By Abinash, 10 years ago, In English

Problem :Link

My Idea :If D = Distance between Two Upper L Block then there are two case

  1. If I make D larger that make the circle larger
  2. If I make D smaller that make the circle larger for upper 'v' block

So this properties make the graph of Distance like 'U' ( Unimodal ) That why I thinks it can be solve by Ternary Search where variable is D here . But don't figure out how to check is circle is larger or smaller when searching ? I checking I have calculate radius of circle for mid values , but how ?

Thanks in Advance !!

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

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

Well, you may google for algorithms for finding the radius of the circumscribed circle for a polygon :).

But this problem can be easily solved using a binary search approach. It's obvious that if 5 L-s can fit in a smaller circle, they will fit in a larger one.

And yes, I won't explain the solution in details, unless asked to do so :).

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

    Please explain the solution in Details :) AlexanderBolshakov

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

      Okay, I'll try to do this.

      Do you know how to solve the following problem: you have a function bool f(double x) that returns false when x < x0 and true when x >= x0, and you need to find x0?

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

        Yes, I will do it by Binary Search easily !!

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

        But how to create that function for this problem which check either radius is bigger or smaller ?

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

          Just take a circle of a fixed radius and try to put the L-s into it. First put two bottommost ones (they must touch the circle). Then put the second layer (they must stand on the top of the previous layer and the gap must be as large as possible). Then check if you can put the remaining one.

          The only difficulty is to determine the lower and upper bound for binary search. Okay, a small hint: if the gap between the L-s from the second layer equals zero, it's definitely a lower bound. If it equals 4 (they already don't stand on the first layer), it's an upper bound. And both of these radii can be found without any computer :).

          → Reply