问题分析

题目要求在一个正方形屋顶上找到一个点，将狗的皮带固定在这个点上，使得狗能够到达所有天窗的中心，且皮带不会延伸到屋顶边缘之外。具体要求如下：

1. 狗能够到达每个天窗的中心，即每个天窗到固定点的距离不超过皮带的长度。
2. 皮带的长度不能超过从固定点到最近屋顶边缘的距离。
3. 固定点必须是整数坐标，且不能是天窗的坐标。
4. 如果找不到满足条件的点，输出“poodle”。

解题思路

1. 输入数据处理

   • 输入测试用例数量 (N)。
   • 对于每个测试用例，输入屋顶边长 (S) 和天窗数量 (H)。
   • 输入每个天窗的坐标 ((X, Y))。

2. 核心逻辑

   • 遍历所有可能的固定点 ((x, y))，其中 (1 \leq x, y < S)（因为固定点不能在边缘上）。
   • 对于每个固定点，计算皮带的最大长度 (len)，即从固定点到最近屋顶边缘的距离的平方。
   • 检查所有天窗是否都能被覆盖：
     • 如果某个天窗到固定点的距离大于 (len)，则该固定点不满足条件。
     • 如果某个天窗的坐标与固定点重合，也不满足条件。
   • 如果找到满足条件的固定点，输出该点的坐标并结束当前测试用例。
   • 如果遍历完所有点仍未找到满足条件的点，输出“poodle”。

3. 优化细节

   • 在找到满足条件的点后，可以直接跳出循环，避免不必要的计算。
   • 使用 min 函数快速计算从固定点到最近边缘的距离。

代码解析

以下是代码的详细解析：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int po[60][2]; // 存储天窗的坐标
int s, n; // s 是屋顶边长，n 是天窗数量

// 检查固定点 (x, y) 是否满足条件
bool solve(int x, int y) {
    // 计算从固定点到最近边缘的距离的平方
    int len = min(min(x, y), min(s - x, s - y));
    len = len * len;

    for (int i = 0; i < n; i++) {
        int xx = po[i][0], yy = po[i][1];
        // 如果固定点与天窗重合，或者某个天窗到固定点的距离大于皮带长度，则不满足条件
        if ((xx == x && yy == y) || ((xx - x) * (xx - x) + (yy - y) * (yy - y)) > len) {
            return false;
        }
    }
    return true; // 所有天窗都能被覆盖，且皮带不会延伸到边缘之外
}

int main() {
    int T;
    scanf("%d", &T); // 输入测试用例数量
    while (T--) {
        scanf("%d%d", &s, &n); // 输入屋顶边长和天窗数量
        for (int i = 0; i < n; i++) {
            scanf("%d%d", &po[i][0], &po[i][1]); // 输入每个天窗的坐标
        }

        bool flag = false; // 标记是否找到满足条件的点
        for (int x = 1; x < s; x++) { // 遍历所有可能的固定点
            for (int y = 1; y < s; y++) {
                if (solve(x, y)) { // 检查当前点是否满足条件
                    flag = true;
                    printf("%d %d\n", x, y); // 输出满足条件的点
                    x = y = s; // 跳出循环
                }
            }
        }
        if (!flag) {
            printf("poodle\n"); // 如果没有找到满足条件的点，输出 "poodle"
        }
    }
    return 0;
}

总结

本题的关键在于：

1. 遍历所有可能的固定点。
2. 检查每个固定点是否满足条件（覆盖所有天窗且不延伸到边缘）。
3. 优化循环，避免不必要的计算。 通过上述方法，可以高效地解决这个问题。