Problem Statement
NOTE: This problem statement contains an image that may not display properly if viewed outside of the applet.
In a one dimensional mountainous landscape you want to build a watchtower. This watchtower must fulfill one condition: it must be possible to oversee the whole landscape from it. The landscape is described by two int[]s positions and heights. The elements of positions are sorted in strictly ascending order. The height at the i-th element of positions is the i-th element of heights; the intermediate heights are obtained by interpolation.
You are allowed to build the watchtower on the landscape wherever you like. To save expenses, you want to build it at a position such that the necessary height of the watchtower needed to oversee the whole landscape is minimized. Return this minimal height.
In a one dimensional mountainous landscape you want to build a watchtower. This watchtower must fulfill one condition: it must be possible to oversee the whole landscape from it. The landscape is described by two int[]s positions and heights. The elements of positions are sorted in strictly ascending order. The height at the i-th element of positions is the i-th element of heights; the intermediate heights are obtained by interpolation.
You are allowed to build the watchtower on the landscape wherever you like. To save expenses, you want to build it at a position such that the necessary height of the watchtower needed to oversee the whole landscape is minimized. Return this minimal height.
Definition
- Class:
- WatchTower
- Method:
- minHeight
- Parameters:
- int[], int[]
- Returns:
- double
- Method signature:
- double minHeight(int[] positions, int[] heights)
- (be sure your method is public)
Notes
- Your return value must have an absolute or relative error less than 1e-9.
Constraints
- positions and heights each contain between 2 and 50 elements, inclusive.
- positions and heights each contain the same number of elements.
- Each element of positions and heights is between 0 and 1,000,000, inclusive.
- The elements of positions are all distinct and sorted in strictly ascending order.
Examples
{ 1,2,4,5,6,7 }{ 1,2,2,4,2,1 }Returns: 1.0
Just build the watchtower at the highest point.{ 10,20,49,59 }{ 0,10,10,0 }Returns: 14.5
Build the watchtower right in the middle.{ 0,2,4,6,8,10 }{ 0,1,3,6,10,11 }Returns: 0.0
A zero height watchtower at position 8 can oversee the whole landscape.
Back to all problems