P9830 [ICPC 2020 Shanghai R] Traveling in the Grid World

考虑一个由 $n$ 行和 $m$ 列组成的网格图案。总共有 $(n+1)\times(m+1)$ 个网格点，即 $n+1$ 条水平线和 $m+1$ 条垂直线的交点。我们将水平线从上到下编号为 $0$ 到 $n$。我们将垂直线从左到右编号为 $0$ 到 $m$。水平线 $i$ 和垂直线 $j$ 的交点命名为 $(i, j)$ ($0\le i\le n, 0\le j\le m$)。 在网格世界中旅行时有一些限制。当你位于点 $(x,y)$ 时，你可以选择一个目的地 $(x',y')$ 并沿着 $(x, y)$ 和 $(x', y')$ 之间的线段走过去。我们称这种操作为一次“行走”。如果在它们之间的线段上存在另一个不同于 $(x, y)$ 和 $(x', y')$ 的网格点，则该行走是被禁止的。你可以走任意多次，但两次连续行走的方向不能相同。（具体来说，如果你从 $(x_0, y_0)$ 走到 $(x_1, y_1)$，然后从 $(x_1, y_1)$ 走到 $(x_2, y_2)$，你必须确保 $(x_0-x_1)(y_1-y_2) eq (x_1-x_2)(y_0-y_1)$。）从 $(x, y)$ 到 $(x', y')$ 的行走长度定义为两个端点之间的欧几里得距离，$\sqrt{(x-x')^2+(y'-y)^2}$。 从 $(0,0)$ 出发，你计划通过几次行走到达 $(n,m)$。由于这些烦人的规则，你可能需要一些转折点来实现你的目标。请找出你的行走的最小总长度。

有多个测试用例。输入的第一行包含一个整数 $T$，表示测试用例的数量。对于每个测试用例： 第一行包含两个整数 $n,m$ ($1\le n,m \le 10^6$)，表示网格图的大小。 保证所有测试用例中 $\max(n,m)$ 的总和不超过 $10^6$。

对于每个测试用例，输出最小的行走总长度。你的答案将被认为是正确的，如果其绝对或相对误差不超过 $10^{-9}$。

题面翻译由 ChatGPT-4o 提供。