2015
04-15

Rolling Hongshu

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.

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).

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).

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

Case 1: 20.62

这道题目也是简单题目，按照能量守恒进行求解就没有问题了；

求出苦土豆到达起点的速度的最大值，并且求出所有山顶到起点的最大速度，取最大即可；

求解坐标有点麻烦，不过可以直接用比例计算，每次可利用二分优化找到对应的最近的山峰。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

typedef struct _point
{
double x,y,v;
double HP;
}point;
point Poin[ 1005 ];
point Tudo[ 1005 ];

int search( double X, int H )
{
int m,l = 1,h = H;
while ( l < h ) {
m = (l+h+1)>>1;
if ( Poin[ m ].x > X )
h = m-1;
else l = m;
}
return h;
}

int main()
{
int T,N,M,W;
scanf("%d",&T);
for ( int t = 1 ; t <= T ; ++ t ) {

scanf("%d%d%d",&N,&M,&W);
for ( int i = 1 ; i <= N ; ++ i )
scanf("%lf%lf",&Poin[ i ].x,&Poin[ i ].y);
for ( int i = 1 ; i <= M ; ++ i )
scanf("%lf%lf%d",&Tudo[ i ].x,&Tudo[ i ].v,&W);

for ( int i = 1 ; i <= M ; ++ i ) {
int s = search( Tudo[ i ].x, N );

if ( Tudo[ i ].x == Poin[ s ].x )
Tudo[ i ].y = Poin[ s ].y;
else
Tudo[ i ].y = Poin[ s ].y + (Poin[ s+1 ].y-Poin[ s ].y)/(Poin[ s+1 ].x-Poin[ s ].x)*(Tudo[ i ].x-Poin[ s ].x);

Tudo[ i ].HP = 40.0*(Tudo[ i ].y-Poin[ 1 ].y) + Tudo[ i ].v*Tudo[ i ].v;
}

double Max = 0;
for ( int i = 1 ; i <= M ; ++ i )
if ( Max < Tudo[ i ].HP )
Max = Tudo[ i ].HP;

for ( int i = 2 ; i <= N ; ++ i ) {
double HP = 40.0*(Poin[ i ].y-Poin[ 1 ].y);
if ( Max < HP ) Max = HP;
}

printf("Case %d: %.2lf\n",t,sqrt(Max));
}
return 0;
}

1. 算法是程序的灵魂，算法分简单和复杂，如果不搞大数据类，程序员了解一下简单点的算法也是可以的，但是会算法的一定要会编程才行，程序员不一定要会算法，利于自己项目需要的可以简单了解。