Kenan drew a plan of the buildings and skywalks along one side of the main avenue of
Baku. There are
The bottom of building
Skywalk
A skywalk and a building intersect if they share a common point. Hence, a skywalk intersects two buildings at its two endpoints, and may also intersect other buildings in between.
Kenan would like to find the length of the shortest path from the bottom of building
One can walk from a skywalk into a building or vice versa at any intersection. If the endpoints of two skywalks are at the same point, one can walk from one skywalk to the other.
Your task is to help Kenan answer his question.
Implementation details
You should implement the following procedure. It will be called by the grader once for each test case.
long long min_distance(std::vector<int> x, std::vector<int> h, std::vector<int> l, std::vector<int> r, std::vector<int> y, int s, int g)
and : integer arrays of length , and : integer arrays of length and : two integers- This procedure should return the length of the shortest path between the bottom
of building and the bottom of building
, if such path exists. Otherwise, it should return .
Examples
Example 1
Consider the following call:
min_distance({0, 3, 5, 7, 10, 12, 14},
{8, 7, 9, 7, 6, 6, 9},
{0, 0, 0, 2, 2, 3, 4},
{1, 2, 6, 3, 6, 4, 6},
{1, 6, 8, 1, 7, 2, 5},
1, 5)
The correct answer is
The figure below corresponds to Example 1:
Example 2
min_distance({0, 4, 5, 6, 9},
{6, 6, 6, 6, 6},
{3, 1, 0},
{4, 3, 2},
{1, 3, 6},
0, 4)
The correct answer is
Constraints
for all for all for all- No two skywalks have a common point, except maybe on their endpoints.
Subtasks
- (
points) - (
points) Each skywalk intersects at most buildings. - (
points) , and all buildings have the same height. - (
points) - (
points) No additional constraints.
Sample grader
The sample grader reads the input in the following format:
- line
: - line
: - line
: - line
:
The sample grader prints a single line containing the return value of min_distance
.
Comments