Problem :Link
My Idea :If D = Distance between Two Upper L Block then there are two case
- If I make D larger that make the circle larger
- 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 !!
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 :).
Please explain the solution in Details :) AlexanderBolshakov
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 returnsfalsewhenx < x0andtruewhenx >= x0, and you need to findx0?Yes, I will do it by Binary Search easily !!
But how to create that function for this problem which check either radius is bigger or smaller ?
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 :).