解题思路

题目要求我们找到一个与给定平行六面体A（边平行于坐标轴）同向且完全包含在A内的平行六面体G，使得G的体积最大且不包含任何给定的点集S中的点（但允许点在边界上）。

关键步骤：

1. 输入处理：读取平行六面体A的尺寸(u, v, w)和点集S的坐标。
2. 切割坐标轴：将点集S的坐标以及A的边界坐标（0和u, v, w）分别添加到x、y、z的切割点集合中，并排序。
3. 生成区间：对于每个坐标轴（x, y, z），生成所有可能的区间（由切割点构成），并按区间长度从大到小排序。
4. 搜索最大体积：遍历所有可能的(x, y, z)区间组合，计算对应的体积，并检查是否包含任何点。如果当前体积已经小于已知最大体积，则提前终止内层循环以优化性能。
5. 输出结果：输出满足条件的最大体积，保留两位小数。

优化点：

• 区间排序：通过将区间按长度从大到小排序，可以在搜索时尽早找到较大的体积，从而利用剪枝条件提前终止不必要的计算。
• 剪枝条件：在遍历区间组合时，如果当前组合的体积已经不可能超过已知最大体积，则跳过剩余的组合。

解决代码

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <iomanip>
#include <tuple>

using namespace std;

struct Interval {
    double low, high, len;
    Interval(double l, double h) : low(l), high(h), len(h - l) {}
};

vector<Interval> generate_intervals(const vector<double>& points) {
    vector<Interval> intervals;
    int n = points.size();
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            intervals.emplace_back(points[i], points[j]);
    sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
        return tie(b.len, a.low, a.high) < tie(a.len, b.low, b.high);
    });
    return intervals;
}

int main() {
    double u, v, w;
    cin >> u >> v >> w;
    int n;
    cin >> n;
    vector<tuple<double, double, double>> points;
    for (int i = 0; i < n; ++i) {
        double x, y, z;
        cin >> x >> y >> z;
        points.emplace_back(x, y, z);
    }

    set<double> x_cuts = {0.0, u}, y_cuts = {0.0, v}, z_cuts = {0.0, w};
    for (const auto& p : points) {
        x_cuts.insert(get<0>(p));
        y_cuts.insert(get<1>(p));
        z_cuts.insert(get<2>(p));
    }

    vector<double> x_list(x_cuts.begin(), x_cuts.end()), y_list(y_cuts.begin(), y_cuts.end()), z_list(z_cuts.begin(), z_cuts.end());
    sort(x_list.begin(), x_list.end());
    sort(y_list.begin(), y_list.end());
    sort(z_list.begin(), z_list.end());

    auto x_intervals = generate_intervals(x_list);
    auto y_intervals = generate_intervals(y_list);
    auto z_intervals = generate_intervals(z_list);

    double max_vol = 0.0;
    for (const auto& x_iv : x_intervals) {
        if (x_iv.len * y_intervals[0].len * z_intervals[0].len <= max_vol && max_vol > 0)
            continue;
        for (const auto& y_iv : y_intervals) {
            double current_xy = x_iv.len * y_iv.len;
            if (current_xy * z_intervals[0].len <= max_vol && max_vol > 0)
                continue;
            for (const auto& z_iv : z_intervals) {
                double vol = current_xy * z_iv.len;
                if (vol <= max_vol && max_vol > 0)
                    break;
                bool valid = true;
                for (const auto& p : points) {
                    double px = get<0>(p), py = get<1>(p), pz = get<2>(p);
                    if (px > x_iv.low && px < x_iv.high && py > y_iv.low && py < y_iv.high && pz > z_iv.low && pz < z_iv.high) {
                        valid = false;
                        break;
                    }
                }
                if (valid)
                    max_vol = max(max_vol, vol);
            }
        }
    }

    cout << fixed << setprecision(2) << max_vol << endl;
    return 0;
}

题意分析

给出一个有顶点为（0，0，0），和（u,v,w)顶点的长方形，不难看出，它有三条边在坐标轴上，再给出一个集合S，现在要求找出一个最大面积的长方体G，各边与A平行，且不与集合S相交（可以在边界上）。

解题思路

可以把集合s中的点（以下称为切割点）投影到三条坐标轴，这些点延长交割形成的图形就是长方体G不能相交的区域。也就是说，这些切割点把原来整体的区间（例如[0，u]）分割成了几个小区间，意味着长方体G的边界不能包含切割点。因为要收集最大体积的长方体G，所以对切割点造成的切割区间进行长度降序排列。接下来需要对切割区间形成的长方体进行枚举，不断更新体积最大的那一个。

标程

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <iomanip>
#include <tuple>

using namespace std;

struct Interval { double low, high, len; Interval(double l, double h) : low(l), high(h), len(h - l) {} };

vector<Interval> generate_intervals(const vector<double>& points) {
    vector<Interval> intervals;
    int n = points.size();
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            intervals.emplace_back(points[i], points[j]);
    sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) {
        return tie(b.len, a.low, a.high) < tie(a.len, b.low, b.high);
    });
    return intervals;
}

int main() {
    double u, v, w; cin >> u >> v >> w;
    int n; cin >> n;
    vector<tuple<double, double, double>> points;
    for (int i = 0; i < n; ++i) {
        double x, y, z; cin >> x >> y >> z;
        points.emplace_back(x, y, z);
    }

    set<double> x_cuts = {0.0, u}, y_cuts = {0.0, v}, z_cuts = {0.0, w};
    for (const auto& p : points) {
        x_cuts.insert(get<0>(p));
        y_cuts.insert(get<1>(p));
        z_cuts.insert(get<2>(p));
    }

    vector<double> x_list(x_cuts.begin(), x_cuts.end()), y_list(y_cuts.begin(), y_cuts.end()), z_list(z_cuts.begin(), z_cuts.end());

    auto x_intervals = generate_intervals(x_list);
    auto y_intervals = generate_intervals(y_list);
    auto z_intervals = generate_intervals(z_list);

    double max_vol = 0.0;
    for (const auto& x_iv : x_intervals) {
        if (x_iv.len * y_intervals[0].len * z_intervals[0].len <= max_vol && max_vol > 0) continue;
        for (const auto& y_iv : y_intervals) {
            double current_xy = x_iv.len * y_iv.len;
            if (current_xy * z_intervals[0].len <= max_vol && max_vol > 0) continue;
            for (const auto& z_iv : z_intervals) {
                double vol = current_xy * z_iv.len;
                if (vol <= max_vol && max_vol > 0) break;
                bool valid = true;
                for (const auto& p : points) {
                    double px = get<0>(p), py = get<1>(p), pz = get<2>(p);
                    if (px > x_iv.low && px < x_iv.high && py > y_iv.low && py < y_iv.high && pz > z_iv.low && pz < z_iv.high) {
                        valid = false;
                        break;
                    }
                }
                if (valid) max_vol = max(max_vol, vol);
            }
        }
    }

    cout << fixed << setprecision(2) << max_vol << endl;
    return 0;
}