尖端放电 - 题解

标签与难度

标签: Brute Force, Hashing, Geometry, Coordinate Geometry, Implementation, Data Structures

难度: 1400

题目大意喵~

主人你好呀，喵~ 这道题是说，在一个大大的网格里，我们放置了 $k$ 座闪闪发光的尖塔。任何两座不同的尖塔之间都会来电，滋啦滋啦~ 这股电流会攻击它们连线的中点位置。

如果一个位置被攻击了两次或者更多次，它就会因为能量过载而“损坏”。我们的任务就是，判断是否存在被损坏的位置。如果存在，就输出 "YES" 和其中一个损坏位置的坐标；如果不存在，就输出 "NO"，很简单对吧？呐，快来和我一起解决它吧！

解题思路分析

喵哈哈，这道题看起来和几何有关，但其实有个小小的魔法可以把它变得很简单哦！让我的耳朵动一动，来捕捉解题的电波，喵~

首先，我们来分析一下“攻击”是怎么发生的。对于两座尖塔，一个在 $(x_i, y_i)$ ，另一个在 $(x_j, y_j)$ ，它们的攻击中点是：

M = \left( \frac{x_i + x_j}{2}, \frac{y_i + y_j}{2} \right)

一个位置被损坏，意味着它至少是两对不同尖塔的中点。比如说，尖塔对 $(A, B)$ 的中点和尖塔对 $(C, D)$ 的中点是同一个位置。我们用数学语言来描述一下就是：

\left( \frac{x_A + x_B}{2}, \frac{y_A + y_B}{2} \right) = \left( \frac{x_C + x_D}{2}, \frac{y_C + y_D}{2} \right)

要让这两个坐标相等，当且仅当它们的 $x$ 分量和 $y$ 分量分别相等，对吧？

\frac{x_A + x_B}{2} = \frac{x_C + x_D}{2} \quad \implies \quad x_A + x_B = x_C + x_D

\frac{y_A + y_B}{2} = \frac{y_C + y_D}{2} \quad \implies \quad y_A + y_B = y_C + y_D

看呀！我发现了什么！我们根本不需要跟烦人的小数打交道，喵！两对尖塔拥有相同的中点，等价于它们横坐标之和相等，并且纵坐标之和也相等！

这下问题就清晰多啦！我们只需要找到两对不同的尖塔，它们的坐标和是相同的。

那么，最直接的思路就是——暴力枚举！就像小猫咪扑向每一个移动的毛线球一样，我们把所有可能的尖塔对都找出来！

遍历所有尖塔对：我们用一个二重循环，遍历所有无序的尖塔对 $(i, j)$ ，其中 $i < j$ 。这样可以保证每对尖塔只被我们考虑一次。
计算坐标和：对于每一对尖塔 $(x_i, y_i)$ 和 $(x_j, y_j)$ ，我们计算出它们的坐标和 sum_x = x_i + x_j 和 sum_y = y_i + y_j。
计数：我们需要一个东西来记录每个坐标和 (sum_x, sum_y) 出现了多少次。
- 如果坐标范围不大，我们可以用一个二维数组 counts[sum_x][sum_y] 来计数。这种方法非常快，就像猫咪的瞬移一样，喵~
- 如果坐标范围很大，二维数组存不下，我们可以用 std::map 或者 std::unordered_map。
判断损坏：每当我们为一个坐标和计数后，就立刻检查它的计数值。如果 counts[sum_x][sum_y] 的值变成了 2，就说明我们找到了第二个拥有这个坐标和的尖塔对。太棒了！这意味着它们的中点是同一个，这个点被攻击了两次，损坏了！
输出结果：一旦找到损坏点，我们就输出 "YES"，然后计算出它的坐标 $(\frac{\text{sum\_x}}{2.0}, \frac{\text{sum\_y}}{2.0})$ 并打印出来。然后就可以结束程序啦。如果所有尖塔对都检查完了，还是没有找到计数值达到 2 的坐标和，那就说明没有位置被损坏，我们安心地输出 "NO" 就好啦。

从参考代码给出的数组大小来看，坐标和的范围是在几千以内，所以使用二维数组是完全可行的，也是效率最高的选择，的说！

代码实现

下面就是我根据这个思路，精心为你准备的代码啦！注释写得很详细，希望能帮到你，喵~

cpp

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

// 定义坐标和的最大值，根据题目数据范围和AC代码推断，5001足够了
// 1 <= x <= n, 1 <= y <= m, n,m <= 2500
// 坐标和的最大值为 2500 + 2500 = 5000
const int MAX_COORD_SUM = 5001;

// 使用静态数组，它会被自动初始化为0，并且不会占用宝贵的栈空间，喵~
int midpoint_counts[MAX_COORD_SUM][MAX_COORD_SUM];

// 解决单个测试用例的函数
void solve() {
    int n, m, k;
    std::cin >> n >> m >> k;

    // 存储尖塔的坐标
    std::vector<std::pair<int, int>> towers(k);
    for (int i = 0; i < k; ++i) {
        std::cin >> towers[i].first >> towers[i].second;
    }

    // 因为有多个测试用例，每次开始前需要重置计数器
    // 注意：这里是一个优化技巧。我们不需要每次都用memset清空整个大数组。
    // 我们可以只清空上次使用过的位置。但为了代码清晰，这里先用一个简单的循环。
    // 更高效的方法是在循环结束后，把你修改过的 `midpoint_counts` 值再清零。
    // 不过对于本题，k较小，直接遍历所有对组，找到答案就退出，所以不需要每次都清空。
    // 我们只需要在找到答案后，为下一个测试用例清理现场。
    // 最简单的方式是记录所有非零点，然后清零。
    // 但由于我们找到答案就返回，一个更简单的策略是，在循环内部处理。
    
    // 储存本次测试用例中所有出现过的中点和，方便之后清理
    std::vector<std::pair<int, int>> used_midpoints;

    bool found = false;
    for (int i = 0; i < k; ++i) {
        for (int j = i + 1; j < k; ++j) {
            // 计算坐标和
            int sum_x = towers[i].first + towers[j].first;
            int sum_y = towers[i].second + towers[j].second;

            // 如果这个中点是第一次出现，记录下来以便清理
            if (midpoint_counts[sum_x][sum_y] == 0) {
                used_midpoints.push_back({sum_x, sum_y});
            }

            // 对应坐标和的计数加一
            midpoint_counts[sum_x][sum_y]++;

            // 如果计数达到2，说明找到了一个损坏点！
            if (midpoint_counts[sum_x][sum_y] >= 2) {
                std::cout << "YES " << std::fixed << std::setprecision(1) 
                          << sum_x / 2.0 << " " << sum_y / 2.0 << "\n";
                found = true;
                break; // 找到了就跳出内层循环
            }
        }
        if (found) {
            break; // 再次跳出外层循环
        }
    }

    if (!found) {
        std::cout << "NO\n";
    }
    
    // 为下一个测试用例清理现场，只清理本次用过的计数
    for(const auto& p : used_midpoints) {
        midpoint_counts[p.first][p.second] = 0;
    }
}

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

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

复杂度分析

时间复杂度: $O(k^2)$ 我们使用了两层嵌套循环来遍历所有可能的尖塔对。尖塔的数量是 $k$ ，所以总共有 $\frac{k(k-1)}{2}$ 对。因此，时间复杂度是 $O(k^2)$ 。对于每个对，我们在二维数组中的操作是 $O(1)$ 的，所以不会增加复杂度，呐。
空间复杂度: $O((\max(n)+\max(m))^2)$ 我们主要的空间开销是 midpoint_counts 这个二维数组。它的维度取决于坐标和的最大值。如果 $n$ 和 $m$ 的最大值为 $C_{max}$ ，那么坐标和的最大值就是 $2 \times C_{max}$ 。所以空间复杂度大约是 $O((2 \times C_{max})^2)$ ，也就是 $O(C_{max}^2)$ 。在本题中，就是 $O(5001 \times 5001)$ 的常数空间。另外，towers 向量占用了 $O(k)$ 的空间，used_midpoints 最多也占用 $O(k^2)$ 的空间，但通常远小于此。主要瓶颈是二维数组。

知识点总结

这道题真有趣，喵~ 它教会了我们几个很棒的技巧：

问题转换：最核心的技巧！把一个看似复杂的几何问题（判断中点是否重合）转换成了一个简单的代数问题（判断坐标和是否相等）。这大大简化了问题，还避免了浮点数精度带来的麻烦。在算法竞赛中，这种转换思想非常重要哦！
用空间换时间：我们通过开一个大大的二维数组 midpoint_counts，实现了对中点出现次数的 $O(1)$ 快速查询和更新。这是典型的“空间换时间”策略，当内存足够时，它能极大地提升程序效率。
数据结构选择：我们讨论了使用二维数组和哈希表（如 std::map）来计数的优缺点。当键的范围可控且不大时，数组（或哈希）是最佳选择；当键的范围很大或类型复杂时，std::map 提供了更大的灵活性。
多测试用例处理：在处理多个测试用例时，要注意清理上一轮留下的数据。我的代码里展示了如何只清理“弄脏”的部分，而不是每次都重置整个大数组，这是一个在处理多组数据时很有用的小优化，喵~

希望这篇题解能让你有所收获，如果还有问题，随时可以再来找我玩哦！喵~

尖端放电 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

代码实现 ​

复杂度分析 ​