2 shunfurh shunfurh 于 2017.09.15 07:14 提问

Two Mountaineers

Description

Two mountain climbers are located at opposite ends of a mountain range, at the same elevation. The two climbers want to walk along the mountain range and reach each other's starting place, while always staying at the same elevation. The climbers may move forward or backward to assure that they stay at the same elevation. It is Well known that it is always possible for the two climbers to reach each other's starting place if the mountain range never drops below the starting elevation. Given a mountain range, compute the minimum sum of the two walk lengths of the two climbers to reach each other's starting place from their own starting place.

Mountain range is represented as a polygonal line P=(p1,p2...,pn) in the plane with point set {pi=(xi,yi):i=1..n} and edge set {(pi,pi+1):i=1...n-1}.The polygonal line P modeling a mountain range is monotone with respect to the x-coordinate axis, i.e., xi
A walk of a climber along a mountain range P is a sequence W={w1,w2,..wm} of points w in P.such that every line-segment of a walk must be on P. We compute the length of a walk along a line-segment , (wj,wj+1) as the difference of the y-coordinates of wj and wj+1. i.e |Yj-Yj+1|.The length of a walk W is the sum of the lengths of the line-segments of W.

For example, in the above figure, the walk of the left climber is (a, d, c, e, g, f, h, j, i, l, o, p, r, p, o, m, o, p, s), and the sum of walk lengths for the two climbers is 120. We can see that the length is the shortest length of walks by the climbers.
Input

The input consists of T test cases. The number of test cases ( T ) is given in the first line of the input file. The first line of each test case contains an integer(3<=n<=1000) , which is the number of points in the polygonal line P. In the following n lines, there are xi, yi(i=1..n) each line.(0<=xi,yi<=10000) One mountain climber starts at p1 , and the other starts at pn . Therefore, the y1=yn. You may assume that for each input test case, the mountain range never drops below the starting elevation and yi is UNIQUE.
Output

For each test case, your program reports, on each line, the minimum length of walks by the two climbers. The following sample input and corresponding correct output represents three test cases.
Sample Input

3
3
0 0
5 5
10 0
5
0 0
2 10
3 5
4 15
5 0
7
5 10
6 15
7 11
8 20
9 12
11 14
13 10
Sample Output

20
100
120

2个回答

caozhy
caozhy   Ds   Rxr 2017.09.16 10:54
已采纳
shen_wei
shen_wei   Ds   Rxr 2017.09.15 16:38
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
POJ 1334 Two Mountaineers 笔记
如图,两个登上者从山的两头开始翻越大山,两人必须保持在相同的海拔上。给出大山的起伏坐标,求两个人翻越大山所走过的y轴距离的总和。
poj3641Pseudoprime numbers Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 8854 Accepte
Pseudoprime numbers Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 8854   Accepted: 3726 Description Fermat's theorem states that for any prime number p and
The only legal comparisons are between two numbers, two strings, or two dates
在freemarker的ftl页面中if标签常常会报freemarker.template.TemplateException: The only legal comparisons are between two numbers, two strings, or two dates.的错误。 解决方法:http://www.yayihouse.com/yayishuwu/chapter/1
Two Sigma面试专题
前段时间过了Two Sigma的第一轮HR面后,就一直没有管,最近准备把Two Sigma的OA做了,不过还是提前准备下,从网上找了几道面经,准备写一写,尽量能过OA面吧,如果过了,下一轮就是技术电话面试。。。以前还从未有过这样的面试,所以想这次试一试。。 Two Sigma NO.1 Friend Circle Problem Statement There
浅析经典面试算法题-two pointer的运用
前几天和朋友讨论 Google 电面的一道题, 由此启发, 总结了下 two pointer 的使用场景, 在大部分情况下, 恰当地使用 two pointer 可以使时间复杂度保持在 O(n), 像 online judge 里部分 medium 题经常提及的子数列类型问题, two pointer 也可以提供不错的切入角度。 前记 前几天和朋友讨论 Google 电面的一道题,
Two Scoops Press Two Scoops of Django 1.11 无水印pdf
Two Scoops Press Two Scoops of Django 1.11 英文无水印pdf pdf所有页面使用FoxitReader和PDF-XChangeViewer测试都可以打开 本资源转载自网络,如有侵权,请联系上传者或csdn删除 本资源转载自网络,如有侵权,请联系上传者或csdn删除
【LeetCode】2. Add Two Numbers 解题报告
转载请注明出处:http://blog.csdn.net/crazy1235/article/details/51820937Subject 出处:https://leetcode.com/problems/add-two-numbers/ You are given two linked lists representing two non-negative numbers. The dig
LInux C语言错误 two or more data types in declaration of `main'
 编译出现错误,一般是 在其前面的代码中,缺少标点符号“;",或者是头文件中,缺少。
LeetCode || Two Sum
Two Sum  Total Accepted: 16363 Total Submissions: 87273My Submissions Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum s
Which two are equivalent? (Choose two)
Which two are equivalent? (Choose two) 2010-04-01 09:31 提问者悬赏:5分 | afeng848 | 分类:英语翻译 | 浏览851次 A. B. C. D. E. F. G. 我有更好的答案 分享到: 1条回答 2013-