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      2017.09.10 23:53

UVA11627

[扫描线 线段树] Codeforces 720D Russian Code Cup 2016 - Finals D. Slalom

UVA11627-Slalom(二分法)

Slalom

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

UVA - 11627 Slalom 二分

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(二分法)

UVA11627 Slalom 障碍滑雪