three points 1 - 题解

标签与难度

标签: 计算几何, 构造, 三角函数, 余弦定理, 暴力枚举

难度: 1600

题目大意喵~

主人你好呀~！这道题是这样的喵：

我们被关在一个二维的矩形小黑屋里，它的范围是从 (0, 0) 到 (w, h)。然后呢，题目给了我们三个正整数 a, b, c。我们的任务是，在这个小黑屋里找到三个点 X, Y, Z，让它们满足：

X 和 Y 之间的距离是 a。
X 和 Z 之间的距离是 b。
Y 和 Z 之间的距离是 c。

这三个点的坐标可以是小数哦！最最最重要的是，题目保证一定存在一个解，所以我们不用担心找不到的情况，只需要把它找出来就好啦，喵~

解题思路分析

这道题看起来是要我们在一个框框里摆一个三角形呢。只知道三条边的长度，却不知道具体坐标，这可怎么办呀？别急，让我来带你一步步解开谜题！

第一步：抓住一个点，把它“锚定”下来！

既然我们只关心点和点之间的相对位置，那整个三角形在小黑屋里是可以自由移动和旋转的。为了简化问题，我们可以先抓住三角形的一个顶点，把它固定在一个方便计算的地方。哪个位置最方便呢？当然是角落里的原点 (0, 0) 啦！它肯定在 [0, w] x [0, h] 的范围内，而且用它来计算其他点的坐标超级简单，喵~

我们就先大胆地假设点 X 的坐标是 (0, 0) 吧！

第二步：安放第二个点

好啦，X 已经乖乖待在 (0, 0) 了。现在我们来处理点 Y。我们知道 Y 离 X 的距离是 a。那么 Y 可以在以 X 为圆心，a 为半径的圆上。为了让第三个点 Z 有尽可能大的空间，一个聪明的策略是把 Y 放在我们小黑屋的边界上。

最简单的想法是把 Y 放在 x 轴上，坐标就是 (a, 0)。

情况1： 如果 a <= w，太棒了！Y 的坐标就可以是 (a, 0)，这个点肯定在小黑屋里。
情况2： 哎呀，如果 a > w 怎么办？Y 就不能放在 (a, 0) 了，因为它跑到墙外面去了！没关系，我们可以把它贴在右边的墙上，也就是让它的 x 坐标为 w。为了保持和 X(0,0) 的距离为 a，根据勾股定理，它的 y 坐标就应该是 $\sqrt{a^2 - w^2}$ $a^{2} - w^{2}$ 。所以 Y 的坐标就是 (w, \sqrt{a^2 - w^2})。
- (小声说：这里我们还要保证 y 坐标不能超过 h，不过题目保证有解，所以在某个正确的构造中，这个条件一定会满足的，我们就先不用太担心啦~)

现在，我们成功地确定了 X 和 Y 的坐标啦！

第三步：用三角魔法召唤第三个点！

万事俱备，只差 Z 点了！我们知道 Z 到 X 的距离是 b，到 Y 的距离是 c。这不就是经典的几何问题——求两圆交点嘛！

但是直接解方程太麻烦了，我更喜欢用优雅的三角函数，喵~

计算角度： 我们可以利用余弦定理，在 $\triangle XYZ$ 中求出 $\angle YXZ$ 的大小。设这个角为 $\alpha$ ，那么根据余弦定理：
$c^2 = a^2 + b^2 - 2ab \cos(\alpha)$
整理一下，就可以得到：
$\alpha = \arccos\left(\frac{a^2 + b^2 - c^2}{2ab}\right)$
确定方向： 我们已经知道了线段 XZ 的长度是 b，以及它和线段 XY 的夹角是 $\alpha$ 。我们还需要知道线段 XY 本身的方向。设线段 XY 与 x 轴正方向的夹角为 $\beta$ 。这个角可以很容易地用 atan2 函数算出来：beta = atan2(y_Y, x_Y)。atan2 是个很棒的函数，它能正确处理所有象限的角度，比 atan 或 acos 更省心！
最终坐标： 现在，线段 XZ 与 x 轴的夹角就是 XY 的角度 beta 加上（或减去）XZ 与 XY 的夹角 $\alpha$ 。我们选其中一个方向就好，比如 theta = beta + alpha。于是，Z 点的坐标就可以通过极坐标转换得到啦：
$x_Z = b \cdot \cos(\theta) \\ y_Z = b \cdot \sin(\theta)$

第四步：万一失败了怎么办？—— 枚举所有可能性！

我们刚刚的推理是基于一个假设：把 X 放在原点，然后放置 Y。但万一这样构造出来的 Z 点跑到了小黑屋外怎么办？

别忘了，题目保证有解！这说明肯定有一种初始摆放方式是可行的。我们刚才的尝试只是其中一种。如果失败了，我们就换一种方式试试！

总共有多少种基本的摆放方式呢？

锚点选择：我们可以选择 X、Y、Z 中的任意一个作为锚点放在 (0,0)。（3种选择）
基准点选择：确定锚点后（比如是 X），我们可以选择与它相邻的另一个点（Y 或 Z）作为第二个放置的基准点。（2种选择）

所以，总共有 $3 \times 2 = 6$ 种基本的构造方案。例如：

X 在原点，先放 Y，再算 Z。
X 在原点，先放 Z，再算 Y。
Y 在原点，先放 X，再算 Z。
Y 在原点，先放 Z，再算 X。
Z 在原点，先放 X，再算 Y。
Z 在原点，先放 Y，再算 X。

我们只需要把这 6 种情况都试一遍，因为题目保证有解，所以其中必定有一种能成功找到在小黑屋里的三个点！找到一个就马上输出，然后就可以开心地解决下一个测试用例啦，喵~

代码实现

这是我根据上面的思路，精心为你准备的代码哦~！注释写得很详细，希望能帮助你理解，喵~

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>

// 使用 long double 来提高浮点数计算的精度，喵~
using LD = long double;

// 定义一个点的结构体，方便存储坐标
struct Point {
    LD x, y;
};

// 全局变量，存储题目给出的信息
LD w, h, dist_xy, dist_xz, dist_yz;
// 存储最终答案的三个点
Point points[4]; 
// 一个小小的误差值，用于浮点数比较
const LD EPS = 1e-9;

// 这是我们的核心函数，尝试一种构造方案
// origin_idx: 放在原点的点的编号 (1, 2, or 3)
// base_idx:   第二个放置的点的编号
// third_idx:  最后计算的点的编号
// d_ob:       原点到基准点的距离
// d_ot:       原点到第三个点的距离
// d_bt:       基准点到第三个点的距离
bool try_placement(int origin_idx, int base_idx, int third_idx, LD d_ob, LD d_ot, LD d_bt) {
    // 1. 将 origin_idx 点放在原点 (0, 0)
    points[origin_idx] = {0.0, 0.0};

    // 2. 计算 base_idx 点的坐标
    Point& base_point = points[base_idx];
    if (d_ob <= w) {
        base_point = {d_ob, 0.0};
    } else {
        // 如果距离超过了宽度 w，就把它贴在右墙上
        LD y_base = sqrt(d_ob * d_ob - w * w);
        // 如果计算出的 y 坐标超出了高度 h，这种放置方式失败
        if (y_base > h + EPS) return false;
        base_point = {w, y_base};
    }

    // 3. 计算 third_idx 点的坐标
    Point& third_point = points[third_idx];
    
    // 使用余弦定理计算夹角 alpha = <base, origin, third>
    LD cos_alpha = (d_ob * d_ob + d_ot * d_ot - d_bt * d_bt) / (2.0 * d_ob * d_ot);
    // 防止因为精度问题导致 acos 的参数超出 [-1, 1] 范围
    if (cos_alpha > 1.0) cos_alpha = 1.0;
    if (cos_alpha < -1.0) cos_alpha = -1.0;
    LD alpha = acos(cos_alpha);

    // 计算基准向量 <origin, base> 与 x 轴的夹角 beta
    LD beta = atan2(base_point.y, base_point.x);

    // 第三个点的方向角 theta = beta + alpha
    LD theta = beta + alpha;

    // 计算第三个点的坐标
    third_point = {d_ot * cos(theta), d_ot * sin(theta)};

    // 4. 检查第三个点是否在矩形框内
    if (third_point.x >= -EPS && third_point.x <= w + EPS &&
        third_point.y >= -EPS && third_point.y <= h + EPS) {
        // 成功啦！输出所有点的坐标
        for (int i = 1; i <= 3; ++i) {
            std::cout << std::fixed << std::setprecision(9) << points[i].x << " " << points[i].y << (i == 3 ? "" : " ");
        }
        std::cout << std::endl;
        return true;
    }

    // 这种构造方式失败了，返回 false
    return false;
}

void solve() {
    std::cin >> w >> h >> dist_xy >> dist_xz >> dist_yz;

    // 尝试 6 种可能的构造方案，直到成功为止
    // 题目保证有解，所以肯定有一个会返回 true
    if (try_placement(1, 2, 3, dist_xy, dist_xz, dist_yz)) return; // X at origin, place Y, find Z
    if (try_placement(1, 3, 2, dist_xz, dist_xy, dist_yz)) return; // X at origin, place Z, find Y
    if (try_placement(2, 1, 3, dist_xy, dist_yz, dist_xz)) return; // Y at origin, place X, find Z
    if (try_placement(2, 3, 1, dist_yz, dist_xy, dist_xz)) return; // Y at origin, place Z, find X
    if (try_placement(3, 1, 2, dist_xz, dist_yz, dist_xy)) return; // Z at origin, place X, find Y
    if (try_placement(3, 2, 1, dist_yz, dist_xz, dist_xy)) return; // Z at origin, place Y, find X
}

int main() {
    // 加速输入输出，让程序跑得更快一点~
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T;
    std::cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: 对于每一个测试用例，我们最多尝试 6 次构造。每一次构造都只包含常数次的数学运算（开方、三角函数等）。所以，每个测试用例的时间复杂度是 $O(1)$ 。如果总共有 $T$ 个测试用例，那么总时间复杂度就是 $O(T)$ 。非常快，喵~
空间复杂度: 我们只需要存储几个变量和三个点的坐标，所用的额外空间是固定的，不随输入规模变化。所以空间复杂度是 $O(1)$ 。

知识点总结

这道题虽然是几何题，但它教会了我们一些很重要的解题思想，呐：

问题简化与转化：面对一个自由度很高的问题（三角形可以任意平移旋转），通过“锚定”一个点到原点，大大降低了问题的复杂度。
构造性思维：不要总想着去解析地求解，有时候一步步地、有策略地去“构造”一个解是更直接有效的方法。
系统性枚举：当一个构造策略有多种选择时（比如选哪个点做锚点），如果可能性不多，可以系统地把它们全部尝试一遍。这是暴力美学的一种体现！
几何工具的应用：熟练运用勾股定理、余弦定理、以及 atan2 这样的三角函数工具，是解决计算几何问题的基本功，要好好掌握哦！
浮点数精度：在处理 double 或 long double 时，要时刻注意精度问题。比如用 EPS 进行范围比较，以及注意 acos 的参数不能超出 [-1, 1]。

希望这篇题解能帮到你！继续加油，享受编程的乐趣吧，喵~！

three points 1 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

第一步：抓住一个点，把它“锚定”下来！ ​

第二步：安放第二个点 ​

第三步：用三角魔法召唤第三个点！ ​

第四步：万一失败了怎么办？—— 枚举所有可能性！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​