【2025ICPC武汉邀请赛】M. 航班追踪器

题目大意

假设地球是一个以 $(0, 0, 0)$为中心、半径为 $r$ 的球体，位于三维欧几里得空间中。一架飞机沿着地球表面从出发地到目的地的最短路径飞行。

作为一名航空爱好者，你有一个接收器，可以接收到与飞机距离不超过 $d$ 的信号。注意，两点之间的距离是通过测量地球表面的最短路径来计算的，而不是三维欧几里得空间中的直线距离。你需要找到最小的 $d$，使得在你的位置放置接收器时，能够在某个时刻接收到飞机的信号。

输入

输入包含多个测试用例。第一行是一个整数 $T$ $(1 \leq T \leq 10^4)$，表示测试用例的数量。对于每个测试用例：

第一行是一个整数 $r$（$1 \leq r \leq 100$），表示地球的半径。

第二行是三个整数 $a, b, c$（$-100 \leq a, b, c \leq 100, a^2 + b^2 + c^2 > 0$），表示你的位置坐标为 $\left( \frac{ra}{\sqrt{a^2 + b^2 + c^2}}, \frac{rb}{\sqrt{a^2 + b^2 + c^2}}, \frac{rc}{\sqrt{a^2 + b^2 + c^2}} \right)$。

第三行是三个整数 $u, v, w$（$-100 \leq u, v, w \leq 100, u^2 + v^2 + w^2 > 0$），表示出发地的坐标为 $\left( \frac{ru}{\sqrt{u^2 + v^2 + w^2}}, \frac{rv}{\sqrt{u^2 + v^2 + w^2}}, \frac{rw}{\sqrt{u^2 + v^2 + w^2}} \right)$。

第四行是三个整数 $x, y, z$（$-100 \leq x, y, z \leq 100, x^2 + y^2 + z^2 > 0$），表示目的地的坐标为 $\left( \frac{rx}{\sqrt{x^2 + y^2 + z^2}}, \frac{ry}{\sqrt{x^2 + y^2 + z^2}}, \frac{rz}{\sqrt{x^2 + y^2 + z^2}} \right)$。

保证出发地和目的地不会重合，也不会位于地球的完全相反位置。因此，从出发地到目的地的地球表面最短路径是唯一确定的。

输出

对于每个测试用例，输出一个实数，表示最小的 $d$，使得在你的位置放置接收器时，能够在某个时刻接收到飞机的信号。

当你的答案的绝对误差或相对误差不超过 $10^{-4}$ 时，答案被视为正确。具体来说，假设你的输出为 $a$，标准答案为 $b$，则当 $\frac{|a - b|}{\max(1, |b|)} \leq 10^{-4}$ 时，答案被接受。

题解

根据地理上学过的知识，球面上两点的最短距离一定是“大圆航线”，意思就是起点和终点这一段形成的圆弧一定是经过球原点的大圆，这个大圆的半径就是球的半径。注意到，从出发地移动到目的地，在一部分情况下，距离你的距离的变化呈现一个凹函数，这个时候就可以用三分了。具体的三分实现就是找一个在 $S$ ， $T$ 之间的向量，由于都过原点，一定保证这个之间的向量在航线的大圆上面，稍微注意一下要把三个点都换成单位向量，还有注意一下c++中acos函数的值域是 $[-1,1]$，由于精度误差可能会略大于 $1$ 或略小于 $-1$ 输出一个 nan，因此需要额外处理一下。

都被经验主义害了😭，赛场上想的直接分情况讨论，按照结论输出答案。但凡M或者F出其中一个就不至于打铁了。

代码

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const double PI = acos(-1.0);
const double eps = 1e-12;

struct point
{
	double x, y, z;
};
typedef point Vector;

point operator+(point a, point b) { return point{a.x + b.x, a.y + b.y, a.z + b.z}; } //+
point operator-(point a, point b) { return point{a.x - b.x, a.y - b.y, a.z - b.z}; } //-
point operator*(point a, double t) { return point{a.x * t, a.y * t, a.z * t}; }		 // 数乘
point operator*(double t, point a) { return point{a.x * t, a.y * t, a.z * t}; }		 // 数乘
point operator/(point a, double t) { return point{a.x / t, a.y / t, a.z / t}; }		 // 数除
double dot(point a, point b) { return a.x * b.x + a.y * b.y + a.z * b.z; }			 // 点积
double len(point a)
{
	return sqrt(dot(a, a));
}

Vector root(point a, point b)
{
	double res1 = a.y * b.z - b.y * a.z;
	double res2 = a.x * b.z - b.x * a.z;
	double res3 = a.x * b.y - b.x * a.y;
	return {res1, res2, res3};
}

Vector norm(point a)
{
	return a / len(a);
}

double angle(point a, point b)
{
	double Cos = dot(a, b) / len(a) / len(b);
	Cos = max(-1.0, min(1.0, Cos));
	return Cos;
}
double r;
double check(point P, point M)
{
	double ang = acos(angle(P, M));
	return ang * r;
}

void slove()
{
	double a, b, c;
	double u, v, w;
	double x, y, z;
	cin >> r;
	cin >> a >> b >> c;
	cin >> u >> v >> w;
	cin >> x >> y >> z;
	point P = norm({a, b, c}), S = norm({u, v, w}), T = norm({x, y, z});
	Vector V = T - S;
	double l = 0, r = 1;
	Vector M1, M2;
	while (r - l > eps)
	{
		double mid1 = l + (r - l) / 3;
		double mid2 = r - (r - l) / 3;
		M1 = S + V * mid1, M2 = S + V * mid2;
		if (check(P, M1) > check(P, M2))
			l = mid1;
		else
			r = mid2;
	}
	cout << fixed << setprecision(18) << check(P, M1) << endl;
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	int T;
	cin >> T;
	while (T--)
		slove();
		
	
	return 0;
}