题目分析

题目要求我们处理一组正方形，这些正方形的边与坐标轴成45度角放置在第一象限，并且每个正方形的底部顶点位于y=0线上。我们需要将这些正方形按顺序放置，并确定哪些正方形从上方看是可见的（即存在至少一个点，从该点向上垂直的直线不与任何其他正方形相交）。

输入输出说明

• 输入：多组测试用例，每组包含正方形的数量n和n个边长（1到30的整数）。输入以0结束。
• 输出：每组测试用例中，按升序输出可见正方形的索引。

解题思路

1. 正方形放置规则：

   • 第一个正方形S₁的左顶点在x=0处。
   • 对于后续正方形Sᵢ（i > 1），其底部顶点的x坐标bᵢ必须满足：
     • bᵢ > bᵢ₋₁；
     • Sᵢ的内部不与之前放置的任何正方形内部相交。
   • 这意味着每个正方形的放置位置需要尽可能靠左，同时不与其他正方形重叠。

2. 可见性判断：

   • 一个正方形Sᵢ是可见的，当且仅当存在一个点p ∈ Sᵢ，使得从p向上垂直的直线不与任何其他正方形相交。
   • 换句话说，Sᵢ不被任何后续的正方形完全覆盖。

3. 算法选择：

   • 我们需要模拟正方形的放置过程，并记录每个正方形的顶点坐标。
   • 对于每个正方形，检查是否存在一个区域没有被后续的正方形覆盖。

标程代码

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

struct Square {
    int index;
    int size;
    double left;
    double right;
};

bool isVisible(const Square& s, const vector<Square>& squares) {
    for (const auto& other : squares) {
        if (other.index == s.index) continue;
        if (other.left <= s.left && other.right >= s.right) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        vector<int> sizes(n);
        for (int i = 0; i < n; ++i) {
            cin >> sizes[i];
        }

        vector<Square> squares;
        double prevRight = 0.0;

        for (int i = 0; i < n; ++i) {
            double side = sizes[i];
            double left = prevRight;
            double right = left + side * sqrt(2);
            squares.push_back({i + 1, sizes[i], left, right});
            prevRight = right;
        }

        vector<int> visible;
        for (int i = 0; i < n; ++i) {
            bool visibleFlag = true;
            for (int j = i + 1; j < n; ++j) {
                if (squares[j].left <= squares[i].left && squares[j].right >= squares[i].right) {
                    visibleFlag = false;
                    break;
                }
            }
            if (visibleFlag) {
                visible.push_back(squares[i].index);
            }
        }

        for (int i = 0; i < visible.size(); ++i) {
            if (i > 0) cout << " ";
            cout << visible[i];
        }
        cout << endl;
    }
    return 0;
}

代码解释

1. 数据结构：

   • Square结构体存储正方形的索引、边长、左边界和右边界坐标。

2. 正方形放置：

   • 根据输入的正方形边长，计算每个正方形的左右边界坐标。由于正方形边与坐标轴成45度角，对角线长度为边长乘以√2。

3. 可见性检查：

   • 对于每个正方形，检查是否存在后续的正方形完全覆盖它（即后续正方形的左右边界完全包含当前正方形的左右边界）。
   • 如果没有被完全覆盖，则该正方形是可见的。

4. 输出结果：

   • 收集所有可见正方形的索引，并按升序输出。

该算法确保了正确性和效率，适用于题目给定的数据范围（n ≤ 50）。