[UVa10122]神秘的山

Grade Open Time Friday, 19 September 2014, 10:08 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:08 am
Allow late Yes Close Time Friday, 26 September 2014, 10:08 am
Input file mysteriousmountain.in Output file mysteriousmountain.out

【题目描述】

一组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