C++2d矩形2d最小面积二叉树装箱，箱子知道长宽，矩形数据为double型，包含ID,长宽，矩形允许旋转 90度，并且返回矩形的摆放位置，代码

以下是C++实现矩形最小面积二叉树装箱的代码，其中包含矩形ID，长宽，是否旋转以及矩形的放置位置和朝向。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>

using namespace std;

struct Rect {
    int id;
    double width;
    double height;
    bool rotated;
    double x;
    double y;
    double angle;

    bool operator<(const Rect& other) const {
        return width > other.width;
    }
};

struct Node {
    Node* left;
    Node* right;
    Rect rect;
    double x;
    double y;

    Node(Rect r) : rect(r), left(nullptr), right(nullptr), x(0), y(0) {}
    ~Node() {
        if (left) delete left;
        if (right) delete right;
    }
};

Node* insert(Node* node, Rect rect, double width, double height) {
    if (!node) {
        node = new Node(rect);
        node->x = 0;
        node->y = 0;
        node->rect.x = node->x;
        node->rect.y = node->y;
        return node;
    }

    if (node->left && node->right) {
        Node* new_node = insert(node->left, rect, width, height);
        if (new_node) {
            return new_node;
        }
        return insert(node->right, rect, width, height);
    } else {
        double w = node->rect.width + rect.width;
        double h = max(node->rect.height, rect.height);
        if (w <= width && h <= height) {
            Node* new_node = nullptr;
            if (!node->left) {
                new_node = new Node(rect);
                new_node->x = node->rect.width;
                new_node->y = 0;
                new_node->rect.x = node->x + new_node->x;
                new_node->rect.y = node->y + new_node->y;
                node->left = new_node;
            } else {
                new_node = new Node(rect);
                new_node->x = 0;
                new_node->y = node->rect.height;
                new_node->rect.x = node->x + new_node->x;
                new_node->rect.y = node->y + new_node->y;
                node->right = new_node;
            }
            return new_node;
        }
    }
    return nullptr;
}

void print_tree(Node* node) {
    if (!node) return;

    cout << "Rect ID: " << node->rect.id << " Width: " << node->rect.width << " Height: " << node->rect.height << " X: " << node->x << " Y: " << node->y;
    if (node->rect.rotated) cout << " Angle: " << node->rect.angle;
    cout << endl;

    print_tree(node->left);
    print_tree(node->right);
}

double pack(vector<Rect>& rects, double width, double height) {
    sort(rects.begin(), rects.end());

    Node* root = nullptr;
    for (auto& rect : rects) {
        Node* node = insert(root, rect, width, height);
        if (!node) {
            root = insert(root, rect, height, width);
            rect.rotated = true;
            swap(rect.width, rect.height);
        }
    }

    print_tree(root);

    delete root;

    return 0;
}

int main() {
    vector<Rect> rects{
        { 1, 20, 10 },
        { 2, 10, 40 },
        { 3, 30, 5 },
        { 4, 5, 30 },
        { 5, 15, 15 },
        { 6, 10, 10 },
        { 7, 20, 20 },
        { 8, 15, 5 },
        { 9, 5, 15 },
        { 10, 10, 5 }
    };

    double width = 50;
    double height = 50;

    pack(rects, width, height);

    return 0;
}

这里使用了最简单的二叉树装箱算法，将每个矩形从大到小排序，然后尝试将它们插入到已有的节点中。如果节点有两个子节点，则先尝试将矩形插入到左子节点中，如果不行则尝试右子节点。如果节点只有一个子节点或没有子节点，则尝试将矩形插入到该节点中。如果插入成功，则将新的矩形节点返回，否则返回nullptr。如果无法放入，则尝试在高度方向上旋转矩形并再次尝试放置。

在每个节点中，存储了矩形以及该节点的坐标，如果矩形被旋转，则还存储了旋转角度。在装箱结束后，打印出每个矩形的摆放位置和朝向。