题意分析

这道题目描述了一个幻灯片和数字匹配的问题。我们需要将一组幻灯片与一组数字进行匹配，每个幻灯片有一个矩形边界，每个数字有一个坐标点。匹配规则是：

1. 每个幻灯片必须包含且仅包含一个数字（数字坐标必须在幻灯片矩形内）
2. 每个数字只能匹配一个幻灯片
3. 需要找出所有确定的匹配对

输入首先给出幻灯片数量n，然后是每个幻灯片的矩形边界(xmin,xmax,ymin,ymax)，接着是n个数字的坐标(x,y)。输出所有可以唯一确定的匹配对。

解题思路

1. 建立包含关系：首先检查每个幻灯片包含哪些数字，建立幻灯片到可能数字的映射关系。

2. 拓扑排序确定唯一匹配：

   • 找出那些只包含一个可能数字的幻灯片，这些匹配是确定的
   • 将这些确定的数字从其他幻灯片的可能数字中移除
   • 重复这个过程，直到没有新的确定匹配被发现

3. 输出结果：将确定的匹配按幻灯片标签排序后输出

这种方法利用了拓扑排序的思想，逐步消除可能性，最终得到确定的匹配关系。

完整代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

struct Slide {
    int xmin, xmax, ymin, ymax;
    char label;
    vector<int> possible_numbers;
};

struct Point {
    int x, y;
    int number;
};

void solve(int n) {
    vector<Slide> slides(n);
    vector<Point> points(n);

    // 读取幻灯片数据
    for (int i = 0; i < n; ++i) {
        cin >> slides[i].xmin >> slides[i].xmax >> slides[i].ymin >> slides[i].ymax;
        slides[i].label = 'A' + i;
    }

    // 读取数字坐标
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
        points[i].number = i + 1;
    }

    // 建立幻灯片与数字的包含关系
    for (int i = 0; i < slides.size(); ++i) {
        for (int j = 0; j < points.size(); ++j) {
            if (points[j].x > slides[i].xmin && points[j].x < slides[i].xmax &&
                points[j].y > slides[i].ymin && points[j].y < slides[i].ymax) {
                slides[i].possible_numbers.push_back(points[j].number);
            }
        }
    }

    // 拓扑排序：逐步确定唯一匹配
    map<char, int> result;
    bool changed;
    do {
        changed = false;
        for (int i = 0; i < slides.size(); ++i) {
            if (slides[i].possible_numbers.size() == 1) {
                int num = slides[i].possible_numbers[0];
                result[slides[i].label] = num;
                changed = true;

                // 从其他幻灯片的可能数字中移除该数字
                for (int j = 0; j < slides.size(); ++j) {
                    vector<int>::iterator it = find(slides[j].possible_numbers.begin(), 
                                                  slides[j].possible_numbers.end(), num);
                    if (it != slides[j].possible_numbers.end()) {
                        slides[j].possible_numbers.erase(it);
                    }
                }
            }
        }
    } while (changed);

    // 输出结果
    static int heap_num = 0;
    cout << "Heap " << ++heap_num << endl;

    if (result.empty()) {
        cout << "none" << endl;
    } else {
        // 按幻灯片标签排序（A, B, C, ...）
        vector<pair<char, int> > sorted_result(result.begin(), result.end());
        sort(sorted_result.begin(), sorted_result.end());

        for (size_t i = 0; i < sorted_result.size(); ++i) {
            cout << "(" << sorted_result[i].first << "," << sorted_result[i].second << ")";
            if (i != sorted_result.size() - 1) {
                cout << " ";
            }
        }
        cout << endl;
    }
    cout << endl;
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        solve(n);
    }
    return 0;
}