OI题库

【题目描述】

一组M个人正在追逐一只奇怪的动物。他们相信它将在一座神秘的山T上停留，因此他们决定爬上这座山看一看。这座山看上去很平常，如下图所示：

山的轮廓由N+1条线段组成。这些线段的端点从左到右编号为0到N+1.也就是说，对于所有0<=i<=N都有x[i]<x[i+1]。另外，y[0]=y[N+1]=0，对于1<=i<=N有1<=y[i]<=1000.

根据他们的经验，这只动物最可能呆在端点1~N之一上。并且……足够有趣的是，他们很快发现M=N，因此每个人都可以选择一个不同的端点来搜寻那只动物。

最初，所有的人都在山脚下（也就是说第i个人在坐标(si,0)）。对于某个人i，他计划先以速度wi向左或右走到某个位置(x,0)（其中x是一个整数——他们可不想花时间来计算准确位置），然后沿着一条直线以速度ci直接爬到终点。当然，这条直线的任意部分不能超过山的轮廓——他们不会飞。他们并不想让这只动物跑掉，因此领队想让最晚到的人尽量早抵达终点。这最快需要多久？

【输入格式】

输入包含不超过10组数据。

每组数据格式如下：

第一行有一个整数N（1<=N<=100）。接下来的N+2行，每行有两个整数xi和yi（0<=xi,yi<=1000），代表第i个端点的坐标。接下来的N行每行有三个整数ci,wi和si，描述一个人（1<=ci<wi<=100,0<=si<=1000）——爬山的速度，走路的速度，最初的位置。输入结束标志为N=0。不必处理此组数据。

【输出格式】

对每组数据，输出一行一个实数，精确到小数点后两位，即最晚到达终点的人最少需要花多长时间。

【样例输入】

3

0 0

3 4

6 1

12 6

16 0

2 4 4

8 10 15

4 25 14

0

【样例输出】

1.43

【提示】

对于样例，第1个人先走到(5,0)再爬到2号端点，第2个人直接爬到3号端点。第3个人走到(4,0)然后爬到1号端点，如下图：

【来源】

UVa10122 Mysterious Mountain