1. 问题分析

我们需要在已有若干不重叠矩形的墙面上，找到一个新的矩形位置，满足：

• 不与任何现有矩形重叠
• 不超出墙面边界
• 存在多解时选择最靠下（y最小）、其次最靠左（x最小）的位置

2. 关键观察

• 候选位置生成：新矩形的左下角只能出现在以下位置：
  • 现有矩形的左右边界延伸线
  • 现有矩形的上下边界延伸线
  • 墙面边界
• 剪枝优化：只需检查关键坐标点形成的网格，无需遍历所有像素点

3. 算法选择

采用离散化+暴力检查的方法：

graph TD
    A[收集所有关键x/y坐标] --> B[排序并去重]
    B --> C[生成候选位置网格]
    C --> D[检查每个候选位置]
    D --> E{是否有效?}
    E -->|是| F[记录最优位置]
    E -->|否| D
    F --> G[输出结果]

4. 具体实现步骤

1. 输入处理：

   • 读取已挂画作的坐标
   • 收集所有x和y方向的边界坐标

2. 离散化处理：

   // 示例代码
   sort(x_coords.begin(), x_coords.end());
   x_coords.erase(unique(x_coords.begin(), x_coords.end()), x_coords.end());
   

3. 候选位置生成：

   • 对每个x坐标和y坐标的组合(x,y)
   • 计算可能的新矩形区域：(x,y)到(x+w',y+h')

4. 有效性检查：

   • 边界检查：不超出墙面
   • 重叠检查：与所有现有矩形无交集

   bool isOverlap(const Rect& a, const Rect& b) {
       return !(a.x2 <= b.x1 || b.x2 <= a.x1 || 
                a.y2 <= b.y1 || b.y2 <= a.y1);
   }
   

5. 最优解选择：

   • 维护当前最优解(best_x, best_y)
   • 按y升序、x升序比较

5. 复杂度分析

6. 优化技巧

1. 提前终止：找到第一个有效位置后不立即退出，继续寻找更优解
2. 智能排序：按y从小到大、x从小到大顺序检查候选位置
3. 快速IO：使用ios::sync_with_stdio(false)加速输入输出

7. 边界情况处理

• 无挂画：直接检查墙面是否容纳新画作
• 新画作尺寸等于墙面：仅当没有挂画时可行
• 最小尺寸画作：1x1的画作总能找到空隙

8. 示例推演

输入：

1
2 10 10
1 1 3 3
7 7 9 9
2 2

处理过程：

1. 收集x坐标：[0,1,3,7,9,10]
2. 收集y坐标：[0,1,3,7,9,10]
3. 检查候选位置：
   • (0,0)→(2,2) ✔
   • (0,3)→(2,5) ✔
   • (3,0)→(5,2) ✔
   • ...
4. 最优解：(0,0)

输出：

0 0

9. 为什么不用高级数据结构？

• 题目限制n≤200，O(n^3)完全可接受
• 使用线段树等结构会增加实现复杂度
• 离散化后暴力检查足够高效

标程

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

struct Painting {
    int x1, y1, x2, y2;
};

bool isOverlap(const Painting& a, const Painting& b) {
    return !(a.x2 <= b.x1 || b.x2 <= a.x1 || a.y2 <= b.y1 || b.y2 <= a.y1);
}

// 自定义 unique 函数替代 C++11 的 std::unique
template <typename T>
typename vector<T>::iterator my_unique(vector<T>& vec) {
    if (vec.empty()) return vec.end();
    
    typename vector<T>::iterator result = vec.begin();
    for (typename vector<T>::iterator it = vec.begin() + 1; it != vec.end(); ++it) {
        if (*it != *result) {
            *(++result) = *it;
        }
    }
    return ++result;
}

void solve() {
    int T;
    cin >> T;
    while (T--) {
        int n, w, h;
        cin >> n >> w >> h;
        
        vector<Painting> paintings(n);
        vector<int> x_coords, y_coords;
        
        // 添加墙面边界作为候选坐标
        x_coords.push_back(0);
        x_coords.push_back(w);
        y_coords.push_back(0);
        y_coords.push_back(h);
        
        for (int i = 0; i < n; ++i) {
            cin >> paintings[i].x1 >> paintings[i].y1 >> paintings[i].x2 >> paintings[i].y2;
            x_coords.push_back(paintings[i].x1);
            x_coords.push_back(paintings[i].x2);
            y_coords.push_back(paintings[i].y1);
            y_coords.push_back(paintings[i].y2);
        }
        
        // 排序并去重坐标
        sort(x_coords.begin(), x_coords.end());
        x_coords.erase(my_unique(x_coords), x_coords.end());
        sort(y_coords.begin(), y_coords.end());
        y_coords.erase(my_unique(y_coords), y_coords.end());
        
        int new_w, new_h;
        cin >> new_w >> new_h;
        
        bool found = false;
        int best_x = INT_MAX, best_y = INT_MAX;
        
        // 检查所有可能的候选位置
        for (size_t i = 0; i < x_coords.size(); ++i) {
            for (size_t j = 0; j < y_coords.size(); ++j) {
                int x = x_coords[i];
                int y = y_coords[j];
                int x_end = x + new_w;
                int y_end = y + new_h;
                
                // 检查是否超出墙面边界
                if (x_end > w || y_end > h) continue;
                
                Painting new_painting;
                new_painting.x1 = x;
                new_painting.y1 = y;
                new_painting.x2 = x_end;
                new_painting.y2 = y_end;
                
                // 检查是否与现有画作重叠
                bool valid = true;
                for (size_t k = 0; k < paintings.size(); ++k) {
                    if (isOverlap(new_painting, paintings[k])) {
                        valid = false;
                        break;
                    }
                }
                
                // 更新最优解
                if (valid) {
                    found = true;
                    if (y < best_y || (y == best_y && x < best_x)) {
                        best_y = y;
                        best_x = x;
                    }
                }
            }
        }
        
        if (found) {
            cout << best_x << " " << best_y << endl;
        } else {
            cout << "Fail!" << endl;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);  // C++98 中使用 0 代替 nullptr
    solve();
    return 0;
}