做不出来的话，会受稻田姬的斥责啦 - 题解

标签与难度

标签: 几何, 哈希表, 数论, 思维题, 组合数学, 二重循环难度: 1600

题目大意喵~

你好呀，未来的算法大师！我是你们的我小助手，喵~ 这次我们要帮助秋静叶和秋穰子解决一个关于小木棍的问题哦！

她们有 N 根长度不同的木棍，想要从中选出四根，搭建一个“好”的四边形笼子。一个“好”的四边形需要满足两个条件：

它必须是凸的。
它必须有一个内切圆，也就是说，要能放一个圆在里面，并且这个圆刚好和四条边都碰到。这种四边形也叫做切向四边形。

我们的任务就是判断，她们到底能不能找到这样的四根木棍呢？输入是木棍的数量 N 和 N 根木棍各自的长度。如果可以，就输出 "YES"，不然就输出 "NO"，很简单对吧？喵~

解题思路分析

嘿嘿，看到“四边形”和“内切圆”，是不是感觉有点几何的味道，脑袋开始嗡嗡作响了呀？别怕别怕，我我来帮你理清思路，其实这个问题藏着一个非常可爱的数学小秘密哦！

关键的几何定理！

这个问题的核心，是一个叫做皮托管定理 (Pitot's Theorem) 的东西。这个定理告诉我们：

一个凸四边形有内切圆的充要条件是，它的两组对边长度之和相等。

也就是说，如果我们选了四根木棍，长度分别是 $a, b, c, d$ ，并且把它们作为四边形的四条边。只要能满足 对边和 = 另一对边和，比如 $a + c = b + d$ ，那么这四根木棍就一定可以组成一个带内切圆的凸四边形！

是不是一下子就从复杂的几何问题，变成了纯粹的数字游戏了呢？喵~

问题的华丽变身！

有了皮托管定理，我们的任务就变了：

在给定的 N 根不同长度的木棍中，是否存在四个不同的木棍，它们的长度（我们叫它们 $l_1, l_2, l_3, l_4$ ）可以分成两对，使得这两对的和相等？

例如，我们能找到四根木棍，长度为 $l_i, l_j, l_k, l_p$ ，使得 $l_i + l_j = l_k + l_p$ 吗？

怎么找到相等的和呢？

最朴素的想法，就是暴力枚举！就像小猫在毛线球里打滚一样，我们可以尝试所有可能的情况。

暴力枚举 ( $O(N^4)$ ): 我们可以用四层循环，从 N 根木棍里选出四根不同的木棍，然后检查它们是否满足 a+d = b+c 这样的条件（假设 $a<b<c<d$ 是排好序的四根木棍）。但是！如果 N 稍微大一点，比如 2000，那 $2000^4$ 会是一个天文数字，电脑会累坏的！所以这个方法太慢了，不可行。
更聪明的办法 ( $O(N^2)$ ): 既然是找 a+b = c+d，我们可以换个角度思考嘛！我们可以先计算出所有两根木棍的长度之和。
想象一下，我们有一个神奇的储物箱（其实就是哈希表啦，比如 C++ 里的 std::unordered_map）。我们用两层循环，遍历所有可能的木棍对 $(a_i, a_j)$ ，其中 $i < j$ 。
- 计算它们的和 S = a_i + a_j。
- 然后去储物箱里看看，之前有没有存放过 S 这个和。
  - 如果储物箱里已经有 S 了，这说明什么？说明我们之前也找到了一对木棍 $(a_k, a_l)$ ，它们的和也是 S！于是我们就找到了 a_i + a_j = a_k + a_l。因为题目保证了所有木棍长度都不同，所以这四个索引 $i, j, k, l$ 一定是互不相同的。太棒了！我们直接输出 "YES" 然后开心地收工！
  - 如果储物箱里没有 S，我们就把这个新的和 S 存进去，告诉储物箱我们找到过这个和。然后继续寻找下一对木棍。
如果两层循环跑完了，我们都没有找到任何一个重复的和，那就说明不存在这样的四根木棍。我们只好遗憾地输出 "NO" 了。

这个方法只需要两层循环，所以时间复杂度是 $O(N^2)$ ，对于 N 在几千的范围内是完全可以接受的！这下稻田姬就不会斥责我们啦，喵~

代码实现

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

cpp

#include <iostream>
#include <vector>
#include <unordered_map>

// 使用我的魔法让输入输出更快，喵~
void fast_io() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
}

void solve() {
    int n;
    std::cin >> n;
    
    // 如果木棍数量少于4根，肯定组不成四边形啦
    if (n < 4) {
        std::cout << "NO\n";
        return;
    }
    
    std::vector<int> sticks(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> sticks[i];
    }
    
    // 这个是我们的神奇储物箱，用来存放所有已经见过的“两根木棍之和”
    // key是和，value我们随便存个true就行，表示这个和出现过
    std::unordered_map<int, bool> seen_sums;
    
    // 开始遍历所有可能的木棍对 (i, j)
    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            // 计算当前这对木棍的和
            int current_sum = sticks[i] + sticks[j];
            
            // 去储物箱里查一查，这个和以前见过吗？
            // .count() 比 .find() 写起来更简洁喵~
            if (seen_sums.count(current_sum)) {
                // 哇！找到了！之前有别的木棍对的和也是这个值！
                // 这就意味着我们找到了 a+b = c+d
                std::cout << "YES\n";
                return; // 任务完成，可以去晒太阳了
            }
            
            // 如果没见过，就把这个和存进储物箱里，做好标记
            seen_sums[current_sum] = true;
        }
    }
    
    // 如果把所有木棍对都检查完了，还是没有找到重复的和
    // 那就说明真的不行啦
    std::cout << "NO\n";
}

int main() {
    fast_io();
    solve();
    return 0;
}

复杂度分析

时间复杂度: $O(N^2)$ 我们使用了两层嵌套循环来遍历所有不同的木棍对。对于一个大小为 $N$ 的数组，大约有 $N(N-1)/2$ 个这样的对。在循环内部，我们对哈希表 unordered_map 的操作（count 和插入）平均时间复杂度是 $O(1)$ 。所以总的时间复杂度由双重循环决定，是 $O(N^2)$ ，非常高效！
空间复杂度: $O(N^2)$ 在最坏的情况下，所有 $N(N-1)/2$ 个木棍对的和都是独一无二的，那么我们的哈希表 seen_sums 就需要存储所有这些和。所以，空间复杂度是 $O(N^2)$ 。

知识点总结

这道题真有趣，从几何到代码，我们学到了不少东西呢，喵~

皮托管定理 (Pitot's Theorem): 这是解决本题的“金钥匙”！它告诉我们，一个凸四边形是切向四边形（有内切圆）的充要条件是其两组对边和相等。记住这个定理，以后遇到类似的几何问题就不怕啦！
问题转化: 学会将一个看似复杂的问题（特别是几何问题）转化为我们熟悉的算法模型（如查找、排序、哈希等）是成为高手的必经之路。
哈希表的妙用: 当你需要快速查找一个元素是否存在于一个集合中时，哈希表（std::unordered_map 或 std::unordered_set）是你的最佳伙伴！它能将查找时间从 $O(N)$ 或 $O(\log N)$ 降低到平均 $O(1)$ ，是解决“寻找重复”或“配对”类问题的强大工具。

希望这篇题解能帮到你！继续加油，你超棒的，的说！喵~

做不出来的话，会受稻田姬的斥责啦 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键的几何定理！ ​

问题的华丽变身！ ​

怎么找到相等的和呢？ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​