CDOJ 27 棒球防守(baseball) 解题报告

题目链接http://acm.uestc.edu.cn/#/problem/show/27

这题是一道数学计算题，比较坑，花了我几天时间

公式推了挺久的，因为看起来麻烦所以放着几天都懒得做...毕竟暑假

题目给的变量名太蛋疼了，我这里作新的约定

防守员的坐标就是((x_0, y_0))，速度(v_0)
滚地球的速度是(v)，沿x轴分速度为(v_x)，y轴分速度为(v_y)
高飞球的落点是((x,y))，飞行时间(t)

难点在于滚地球，要求是只要某个内场的恰好碰到球或者提前到达轨迹才可以

不要求在内场碰到，我一开始以为是在内场碰到滚地球

这样的话题目就变成了求一个某个二次函数在(left[0, frac{r}{sqrt{x^2+y^2}} ight])有没有解的情况

如果不在内场就简单多了，只要求某个二次函数在([0, +infty))有没有解即可

先讲高飞球，很简单，计算一下(sqrt{(x-x_0)^2+(y-y_0)^2})和(vt)的关系即可

这个关系式简单吧，我觉得不需要解释

然后是滚地球，要使人球能接触，则要求内场防守员跑到球的时间(t)满足以下条件[sqrt{(v_xt-x_0)^2+(v_yt-y_0)^2}le v_0t]

这是个关于t的二次不等式，我们将两边平方并移项合并，且因为(v_x^2+v_y^2=v^2)，得：[(v^2-v_0^2)t^2-2(v_xx_0+v_yy_0)t+(x_0^2+y_0^2)le0]

很漂亮的不等式，只要这个不等式在(tin [0,infty))有解即可

当(vge v_0)时，这是显然有解的

当(v < v_0)时，函数(f(t)=(v^2-v_0^2)t^2-2(v_xx_0+v_yy_0)t+(x_0^2+y_0^2))的对称轴为(t_0=frac{v_xx_0+v_yy_0}{v^2-v_0^2} > 0)

所以只需要

[
egin{align*}
Delta&=4(v_xx_0+v_yy_0)^2-4(v^2-v_0^2)(x_0^2+y_0^2)\
&=4(v_x^2x_0^2+v_y^2y_0^2+2v_xv_yx_0y_0-v^2x_0^2-v^2y_0^2+v_0^2x_0^2+v_0^2y_0^2)\
&=4[v_0^2(x_0^2+y_0^2)-v_y^2x_0^2+2v_xv_yx_0y_0-v_x^2y_0^2]\
&=4[v_0^2(x_0^2+y_0^2)-(v_yx_0-v_xy_0)^2]geq0
end{align*}
]

亦即(v_0^2(x_0^2+y_0^2)geq(v_yx_0-v_xy_0)^2)

所以综上所述，只要一个内场防守员满足(vge v_0)或(v_0^2(x_0^2+y_0^2)geq(v_yx_0-v_xy_0)^2)打击者就out

所以打成代码如下

#include <cstdio>
#include <cmath>
using namespace std;

#define EPS (1e-8)

int N, M;
int X[10], Y[10], V[10];
char ball;
double XX, YY, T;
int H, L, VV;
double vx, vy;
bool safe;

inline double sqr(double x) {
	return x * x;
}

int main() {
	while (scanf("%d%d", &N, &M) && N && M) {
		for (int i = 0; i < N; ++i)
			scanf("%d%d%d", &X[i], &Y[i], &V[i]);
		while (M--) {
			safe = true;
			while ((ball = getchar()) != 'F' && ball != 'G');
			switch (ball) {
				case 'G':
					scanf("%d/%d%d", &H, &L, &VV);
					vx = VV * L / sqrt(sqr(H) + sqr(L));
					vy = VV * H / sqrt(sqr(H) + sqr(L));
					for (int i = 0; i < N; ++i)
						if (sqr(X[i]) + sqr(Y[i]) < 400)
							safe &= VV > V[i] && (sqr(X[i]) + sqr(Y[i])) * sqr(V[i]) < sqr(X[i] * vy - Y[i] * vx);
					break;
				case 'F':
					scanf("%lf%lf%lf", &XX, &YY, &T);
					for (int i = 0; i < N; ++i)
						safe &= sqr(XX - X[i]) + sqr(YY - Y[i]) > sqr(V[i] * T);
					break;
			}
			if (safe) puts("SAFE"); else puts("OUT");
		}
	}
	return 0;
}