2 shunfurh shunfurh 于 2017.08.27 17:16 提问

Slalom

In spite of the scarcity of snowfall in Madrid, interest in winter sports is growing in the city, especially with regard to skiing. Many people spend several weekends or even full weeks improving their skills in the mountains.

In this problem we deal with only one of the multiple alpine skiing disciplines: slalom. A course is constructed by laying out a series of gates, which are formed by two poles. The skier must pass between the two poles forming each gate. The winner is the skier who takes the least time to complete the course while not missing any of the gates.

You have recently started to learn to ski, but you have already set yourself the goal of taking part in the Winter Olympic Games of 2018, for which Madrid will presumably present a candidature. As part of the theoretical training, you need to write a program that calculates, given a starting point and a series of gates, the minimum-length path starting from the point given and passing through each gate until you reach the last one, which is the finish line. You may assume that the gates are horizontal and are ordered from highest to lowest, so that you need to pass through them in order. You consider yourself an accomplished skier, so you can make any series of turns, no matter how difficult, and your only concern is minimizing the total length of the path.

Input

The first line of each case gives the number of gates n(1 ≤ n ≤ 1000). The next line contains two floating point numbers, the Cartesian coordinates x and y of the starting position, in that order. Next come n lines with three floating point numbers each, y, x1, x2, meaning that the next gate is a horizontal line from (x1 , y) to (x2 , y). You can safely assume that x1 < x2 . The values of y are strictly decreasing and are always smaller than that of the starting position. The last gate represents the finish line. All coordinates are between −500000 and 500000, inclusive. A value of 0 for n means the end of the input. A blank line follows each case.

Output

For each test case, output a line with the minimum distance needed to reach the finish line. Your answer should be accurate to within an absolute or relative error of 10−7.

Sample Input

2
0 2
1 1 2
0 0.5 3

3
0 4
3 1 2
2 -1 0
1 1 2

0
Sample Output

2.41421356237
4.24264068712

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.10 23:53
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
UVA11627
题目大意:你正在参加一个障碍滑雪比赛,由山头滑向山脚。途中必须经过若干宽度为W的门。你的横向移动速度是已知的。现在给定若干滑雪板,他们有不同的垂直速度,请你选择一款滑雪板,使得能够最快的完成比赛。 将滑雪板按速度排序之后进行二分。由于一开始可以站在任意点,所以第一个门范围内的任意点我们都是可以到达的,然后计算到达下一个门的时间,再根据横向移动速度,可以计算出到达下一个门时,我们能到达的范围区间,
[扫描线 线段树] Codeforces 720D Russian Code Cup 2016 - Finals D. Slalom
注意这里的本质不同的含义 是左边和右边的障碍集合不同 那么我们要考虑怎么去重 我们要求能向右走就向右走 也就是说我们考虑把所有向左上的角都折叠起来然后就可以扫描线加线段树了 我们遇到一个障碍 就把能爬上来的都统计到障碍上面的那格 注意能爬需要一些判断#include<cstdio> #include<cstdlib> #include<algorithm> #include<set> usi
UVA11627-Slalom(二分法)
题目链接 题意:有n个宽为w的旗门,第i个旗门左端的坐标为(xi, yi),对于所有1 思路:当垂直速度越小时,到达下一个旗门的概率就越大。所以先将滑雪板的速度从小到大排序。其实一个旗门到下一个旗门是有一个区间的,所以只要下一个旗门与这个区间有交集,就代表能从上一个抵达下一个,我们就可以根据这个做法加上二分法查找能通过所有旗门的最大速度。 #include #includ
Slalom
题意: 给出每个门起点,高度和横向长度以及滑板的垂直速度,水平速度恒定,求出能取的最快滑板速度. 思路: 二分确定最快速度,由于门的高低递增,所以检查速度是否可行时从后往前,看通过下个门的高度临界值时是否可以通过门. 代码:#include #include #include using namespace std; int w, v, n; struct door { double x
UVA 11627(p80)----Slalom
#include #define debu using namespace std; const int maxn=1e6+50; int maxx,w,vh,n,s,ans,tmp; int x[maxn],y[maxn],ski[maxn]; int check(int speed) { double l=(double)x[0],r=(double)(x[0]+w); for
codeforces 720D. Slalom
细节炸的好惨…根据只能向上或者向右走的性质,我们考虑一种朴素的做法 令f[i][j]表示走到第i列,第j行的路径数 这样做时间复杂度是O(nm)O(nm)的,而且会算重复一些路径,因为对于每个障碍的位置关系都相同的路径是视为同一路径的 先考虑怎么去重 每条路径,除非需要绕过障碍,否则我们都让他保持最低的高度,即贴着底线走,由于其只能向上或右走的性质,别的走法能走到的地方这样走也都能走到,且在
UVA - 11627 Slalom 二分
题目大意: 在一场滑雪比赛 中,你需要通过n个旗门,第i个旗门左端的坐标为(xi,yi),所有旗门的宽度均为W。旗门的海拔高度严格递减,即对所有1 解题思路:二分枚举能通过的最大速度。因为竖直速度是不变的,就可以求出能移动的水平距离的范围,可以判断这个范围是否在旗门之内,如果不在的话,表示速度太大。 #include #include using namespace std; #define
UVa 11627 Slalom (二分)
You are competing in a ski slalom, and you need to selectthe best skis for the race. The format of the race is that there areNpairs of left and right gates, where each right gate isW metres to the rig
UVA - 11627 - Slalom(二分法)
思路很明显,对于一个确定的v 从第一个线段出发,最多能到达的区间为 (l-((y[i+1]-y[i])*hv*1.0)/v ,  r+((y[i+1]-y[i])*hv*1.0)/v) 然后与下一个线段相交即可。 那么二分上线就可以了。 #include #include #include #include #include #include #include #include
UVA11627 Slalom 障碍滑雪
题意在一场滑雪比赛中要通过n个门,给出每个门的坐标(xi,yi)。数据给出w(每个门的宽度),v(水平方向上的最大速度),以及n。 然后是n行门的坐标。在给出m,表示有m双滑雪鞋,每双鞋的速度为s[i]。 问:可以通过所有旗门的滑雪板的最大速度。 解析首先现将s[i]排序,然后二分答案。判断只需要更具前后两个旗门的高度差来计算时间,由上一个可达区间推出下一个可达区间,然后判断上一个区间和下