poj 3684 Physics Experiment 弹性碰撞

缘起

日常浪费生命 poj 3684 Physics Experiment

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
用N个半径R厘米的球进行如下实验.
H米高的位置放置一个圆筒. 将球垂直放入（从下往上数第1个球的底部距离地面的高度为H）.实验开始时最下面的
球开始掉落，此后每秒钟又有一个球开始掉落. 不计空气阻力，并假设球和球、球和地面的碰撞都是弹性碰撞。
请求出实验开始后T秒钟每个球底部距离地面的高度。假设重力加速度是g=10m/s^2

【输入】
多样例. 第一行就是样例数. 然后每个样例有 N H R T 四个整数
1≤ N ≤ 100.
1≤ H ≤ 10000
1≤ R ≤ 100
1≤ T ≤ 10000

【输出】
每个样例输出N个浮点数（精确到小数点后2位，单位是米）表明每个球的底部距离地面的高度

【样例输入】
2
1 10 10 100
2 10 10 100

【样例输出】
4.95
4.95 10.20

【限制】
1s

【来源】
poj月赛

其实本题和【1】非常类似. 如果模拟的话，会死人的. 但是因为是弹性碰撞, 所以其实就是N个球，按照图中的状态出发进行自由落体. 然后每个球就好像其他球不存在那样进行运动. 求T秒之后它所处在的高度.求出了每个高度之后，再排序即可. 就是原本的球的高度. 而求T秒后球的高度这就需要一点物理知识了. 因为不损失能量.

使用能量守恒+动量定理， 可以得到如下方程组, 假设球从h处自由落体t秒钟. 不难根据动量定理知道每次地面给球的动量是垂直向上的 2mv=2m*g*sqrt(2h/g), 所以有(下面的v假设与重力是一个方向), n是和地面弹性碰撞的次数.

$$
\begin{cases}
\frac{1}{2}mv^2=mgh-mgx \
mv=mgt-n2mg\sqrt{2h/g} \
n = 0（如果t<=\sqrt{2h/g}）,或者1+(t-\sqrt{2h/g})/(2\sqrt{2h/g}), 如果t>\sqrt{2h/g}的话
\end{cases}
$$

这个方程组的求解也是极为简单的. 首先确定n, 然后根据第二个确定v, 最后根据第一个确定x. 本题另一个考察点就是浮点数的处理.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include "stdafx.h"

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
#define LOCAL
const double eps = 1e-6, g = 10.0;
int n,h,r,t;
double hs[105]; // 用于存储t秒后各个求的高度

double kk(double height, int time) //一个球从距离地面height处开始自由落体time秒钟. 方法返回它处在的高度
{
	double tt = sqrt(2*height/g); // 单趟自由落体时间
	int nn = time<(tt+eps)?0:1+(int)((time-tt)/(2*tt)+eps); // 计算弹性碰撞次数(time<=tt的话, 就是0次)
	double v = g*time-nn*2*sqrt(2*g*height); // 计算time之后的速度
	return height-v*v/(2*g); // 计算time之后的高度
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%d%d%d%d", &n, &h, &r, &t);
		for (int i = 0; i<n;i++) // 逐个确定每个球的高度
		{
			if (t>=i)
			{
				hs[i] = kk(h+0.02*r*i, t-i); // 第i个球下落的高度是h+2r*i, 下落了t-i秒钟
			}
			else // 根本没下落
			{
				hs[i] = h+0.02*r*i;
			}
		}
		sort(hs, hs+n);
		for (int i = 0; i<n;i++)
		{
			if (i)
			{
				putchar(' ');
			}
			printf("%.2lf", hs[i]);
		}
		puts("");
	}
	return 0;
}

然鹅，连他妈的给出的样例输入都过不了~ 死想了一会儿才想明白为什么这种做法是错误的——因为球有半径. 两球碰撞然后分开，将彼此视作自己的延续（弄懂此题的核心思想你会知道我在说什么的）.但是瞬间移动了2R的距离啊! 所以网上很多题解才先考虑的是R=0，再把2R加上去的缘故.

ac代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//#include "stdafx.h"

#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
//#define LOCAL
const double eps = 1e-6, g = 10.0;
int n,h,r,t;
double hs[105];

double kk(double time) // 注意, 这里的入参是double的! 
{
	double ret;
	double tt = sqrt(2*h/g); // 单趟自由落体时间
	int nn = (int)(time/tt+eps);
	time-=nn*tt; // 如果time不是double而是int的话, 则time就丢失了精度——因为tt是浮点数!
	if (nn & 1) // 奇数趟
	{
		ret = time*sqrt(20.0*h)-5*time*time; // 记住~ 求的是到地面的距离,而不是下落了多少距离!  这里用了匀加速位移公式 vt+1/2*a*t^2
	}
	else // 偶数趟
	{
		ret= h-5*time*time;
	}
	return ret;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	while(kase--)
	{
		scanf("%d%d%d%d", &n, &h, &r, &t);
		for (int i = 0; i<n;i++)
		{
			if (t>=i)
			{
				hs[i] = kk(1.0*(t-i)); // 这里改动了——将R视作0
			}
			else // 根本没下落
			{
				hs[i] = h;
			}
		}
		sort(hs, hs+n);
		for (int i = 0; i<n;i++)
		{
			if (i)
			{
				putchar(' ');
			}
			printf("%.2lf", hs[i]+0.02*r*i);// 注意, 这里  0.02*r*i要最后加, 不能在上面44行就加, 因为根本没确定哪个球是哪个球
		}
		puts("");
	}
	return 0;
}

ac情况

Status Accepted
Time 16ms
Memory 128kB
Length 1044
Lang C++
Submitted 2019-09-02 16:32:35
Shared
RemoteRunId 20825628

唉，此题做了好久~ 思路到是一下子就想到了~ 囧~

参考

【1】https://yfsyfs.github.io/2019/08/15/poj-1852-Ants-%E6%8E%92%E5%BA%8F/