ZOJ 1104 Leaps Tall Buildings

题目大意：给出一些建筑物的高度与宽度，求出一条最矮的抛物线运动轨迹，能够跨过所有的建筑物。

输出初速度与水平方向的夹角，以及初速度的大小。

重力加速度取9.8m/(s^2）

思路：

因为该抛物线过固定点（0,0）和（D,0）（D为所有建筑物宽度之和），故设抛物线方程为：

y = A * x * ( x - D )

建立直角坐标系，得到最高的那一圈点的坐标。

例如第二组样例：

0 10.5

20 11.5

25 10

10 15

0 7

其对应坐标为：

(10.500000, 20.000000)

(22.000000, 25.000000)

(32.000000, 25.000000)

(47.000000, 10.000000)

(54.000000, 0.000000)

从第一个点枚举到第 n-1 个点求得不同的A，分别验证是否满足条件，在满足条件的抛物线中选择顶点最小的那一条。

角度angle = arctan(抛物线在(0,0)点的导数);

运用高中物理知识……

(g*t*t) / 2 = 抛物线顶点高度 => 求出 t

速度= g * t / sin(angle)

 1 #include <cstdio>
 2 #include <cmath>
 3 
 4 const int MAXN = 100 + 10;
 5 const double INF = 1 << 30;
 6 const double PI = acos(-1);
 7 
 8 struct point
 9 {
10     double x, y;
11 };
12 
13 int n;
14 double A, D;
15 double maxHeight;
16 point P[MAXN];
17 double h[MAXN], d[MAXN];    //开始的时候一定要分开保存，我一开始直接读的点的坐标，结果WA了好几次
18 
19 double getA( double x, double y )   //根据第三个坐标点得到A的值
20 {
21     return y / ( x * ( x - D ) );
22 }
23 
24 double getY( double x, double tpA )  //根据当前的抛物线方程，给出横坐标x，返回纵坐标y
25 {
26     return tpA * x * ( x - D );
27 }
28 
29 double Judge( double tpA )          //判断该抛物线是否满足条件
30 {
31     for ( int i = 1; i < n; i++ )
32     {
33         double tt = getY( P[i].x, tpA );
34         if ( tt < P[i].y ) return -1;   //如果该x对应抛物线上的y值 小于该点坐标的y值，则不符合条件
35     }
36 
37     double pp = getY( D/2.0, tpA );
38     return pp;                     //若满足，返回最高点高度
39 }
40 
41 void FindMin()
42 {
43     D = d[n];
44     maxHeight = INF;
45     for ( int i = 1; i < n; i++ )
46     {
47         double H;
48         double tpA = getA( P[i].x, P[i].y );
49 
50         H = Judge( tpA );
51 
52         if ( H > 0 && H < maxHeight )       //如果该抛物线符合条件，并且小于当前的最大值，则更新
53         {
54             maxHeight = H;
55             A = tpA;
56         }
57     }
58     return;
59 }
60 
61 int main()
62 {
63     d[0] = h[0] = 0;
64 
65     while ( scanf("%d", &n) != EOF )
66     {
67         double a;
68         for ( int i = 1; i <= n; i++ )
69         {
70             scanf("%lf%lf", &h[i], &a);
71             d[i] = d[i - 1] + a;
72         }
73 
74         for ( int i = 1; i < n; i++ )         //得到最外面那一圈点的坐标
75         {
76             P[i].x = d[i];
77             P[i].y = h[i] > h[i + 1] ? h[i] : h[i + 1];   
78         }
79 
80         FindMin();
81 
82         double angle = atan( - A * D );       //这里得到的角度是弧度，还应当转化一下
83 
84         double temp = A * ( D/2.0 ) * ( D/2.0 - D );
85         double t = sqrt( temp / 4.9 );
86         double v = 9.8 * t / sin(angle) ;
87 
88         printf("%.2f %.2f\n", angle * 180 / PI,  v);
89 
90     }
91 
92     return 0;
93 }