WatchTower
SRM 240 · 2005-04-30 · by Jan_Kuipers
SRM 240 · 2005-04-30 · by Jan_Kuipers · Geometry
Problem Statement
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 twoint[] 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
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.
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
0)
{ 1,2,4,5,6,7 }
{ 1,2,2,4,2,1 }
Returns: 1.0
Just build the watchtower at the highest point.
1)
{ 10,20,49,59 }
{ 0,10,10,0 }
Returns: 14.5
Build the watchtower right in the middle.
2)
{ 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.
3)
{ 0,1,2,3,4,5,6,7,8,9,10 }
{ 0,1,0,1,0,1,0,1,0,1,0 }
Returns: 4.0
4)
{ 0, 250000, 500000, 750000, 1000000 }
{ 1000000, 900000, 10000, 900000, 1000000 }
Returns: 0.0
5)
{0,1000000}
{30581,170681}
Returns: 0.0
My girlfriend's and my birthday;)
Submissions are judged against all 47 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class WatchTower with a public method double minHeight(vector<int> positions, vector<int> heights) · 47 test cases · 2 s / 256 MB per case