编程介的小学生 2020-02-16 02:05 采纳率: 20.5%
浏览 92

Rolling Hongshu 的算法

Problem Description
To see his girl friend, sweet potato has to go over thousands of mountains. What make things worse, many bitter potatoes lives in these mountains. They hate sweet potato because they don't have girl friends.

In the world of potatoes, friction force does not exist. So the way potatoes travel is very simple: they start with an initial speed, rolling forward and waiting to get to the destination.

Bitter potatoes lived in different places. When sweet potato rolls passing their home, they begin to chase him (surely by rolling with an initial speed). If sweet potato is caught by a bitter potato, his date with girl friend has to be canceled.

Now sweet potato wants to know the minimum initial speed necessary to see his girl friend.

Input
First line is an integer T (T ≤ 50), the number of test cases.

At the beginning of each case is three integers, N, M and w, indicate the number of peaks in the mountains, the number of bitter potatoes and the weight of sweet potato separately.

2 ≤ N ≤ 1000, 0 ≤ M ≤ 1000, 0 < w < 100000.

The next N lines each contain a pair of integers. Each pair of integers xi, hi describe a peak. xi is the horizontal distant between sweet potato's home and the peak. hi is the height of the peak. All xi are different. 0 = x1 < x2 < … < xn ≤ 100000000, -100000000 ≤ hi ≤ 100000000. Between adjacent peaks is a smooth slope. The bitter potatoes are on these slopes.

The following M lines each contain 3 integers. Each triple of integers pi, vi, mi describe a bitter potato. pi is the horizontal distant between his home and sweet potato’s home. vi is his initial speed. mi is his weight. 0 < pi < xn, 0 ≤ vi ≤ 100000000, 0 < mi < 100000

The gravitational constant in potatoes' world is 20.

Sweet potato's home is at point (x1, h1). His girl friend lives at point (xn, hn).

Output
For each case, you should output “Case k: ” first. Following a number, the lower bound of sweet potato's initial speed rounded to two decimal places.

Sample Input
1
6 2 100
0 0
2 5
3 2
4 1
5 3
8 -2
2 15 100
5 11 100

Sample Output
Case 1: 20.62

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
    • ¥15 解riccati方程组
    • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
    • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
    • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
    • ¥50 树莓派安卓APK系统签名
    • ¥65 汇编语言除法溢出问题
    • ¥15 Visual Studio问题
    • ¥20 求一个html代码,有偿
    • ¥100 关于使用MATLAB中copularnd函数的问题