Rolling Hongshu
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65768/65768 K (Java/Others)
Total Submission(s): 1230 Accepted Submission(s): 367
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
Source
The 36th ACM/ICPC Asia Regional Chengdu Site —— Online Contest
解题报告：这道题就是典型的物理题，求sweet potato速度的最小值，题意就是sweet potato要见girl friend，但是中间有bitter potato，只要bitter potato追不上sweet potato，sweet potato才能见他的girl friend，思路就是想让sweet potato能越过最高的拐点，如果sweet potato到达bitter potato位置时的动能比bitter potato大，bitter potato才最不上sweet potato；（其中质量以bitter potato为标准）；
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
const int MAX = 1010;
const double g = 20.0;
double W;
struct node//存储拐点的信息其中peak[0]存储的是sweet potato的位置peak[n - 1]是girl friend的位置
{
double x;
double h;
}peak[MAX];
struct pode//存储bitter potato的位置
{
double p;
double v;
double m;
}point[MAX];
double Max(double x, double y)
{
if (x > y)
{
return x;
}
else
{
return y;
}
}
int T, N, M;
double engin;//存储sweet potato的动能
void Judge(double p, double v)
{
double high;
int i;
if (p == peak[0].x)//如果横坐标正好等于sweet potato的横坐标时
{
high = peak[0].h;
}
for (i = 1; i < N; ++i)
{
if (p == peak[i].x)//如果横坐标等于第i个拐点的横坐标时，说明高度正好等于拐点的高度
{
high = peak[i].h;
break;
}
else if (peak[i - 1].x < p && peak[i]. x > p)//在拐点的中间的时候，
{
double a, b;//y=a* x + b,根据两点式求出a和b;
a = (peak[i].h - peak[i - 1].h) / (peak[i].x - peak[i - 1].x);
b = (peak[i].x * peak[i - 1].h - peak[i - 1].x * peak[i].h) / (peak[i].x - peak[i - 1].x);
high = a * p + b;//bitter potato的高度
break;
}
}
double temp;
temp = W * g * (high - peak[0].h) + 0.5 * W * v * v;//bitter potato的动能，一开始的时候没有注意high要减去peak[0].h，
//动能应该是相对于sweet potato的动能WA了一次
if (temp > engin)//若bitter potato的动能大于sweet potato的动能时
{
engin = temp;
}
}
int main()
{
int i, num = 1;
double ans, maxhigh;
scanf("%d", &T);
while (T --)
{
memset(peak, 0, sizeof(peak));
memset(point, 0, sizeof(point));
scanf("%d%d%lf", &N, &M, &W);
scanf("%lf%lf", &peak[0].x, &peak[0].h);
maxhigh = peak[0].h;
for (i = 1; i < N; ++i)
{
scanf("%lf%lf", &peak[i].x, &peak[i].h);
maxhigh = Max(maxhigh, peak[i].h);//求拐点的最高
}
if (maxhigh <= peak[0].h)//若拐点都处于sweet potato的下面时
{
engin = 0;//sweet potato的初始动能
}
else
{
engin = W * g * (maxhigh - peak[0].h);//sweet potato的初始动能
}
for (i = 0; i < M; ++i)
{
scanf("%lf%lf%lf", &point[i].p, &point[i].v, &point[i].m);
Judge(point[i].p, point[i].v);
}
ans = sqrt(2 * engin / W);//根据动能= 0.5 * M * v * v;求速度
printf("Case %d: %.2lf\n", num, ans);
num ++;
}
return 0;
}