C++二维装箱算法，箱子可以旋转，返回每个箱子的位置和是否旋转，注意数据是double

二维装箱问题是NP完全问题，因此没有一种通用的算法可以在多项式时间内解决。但是，有许多启发式算法和近似算法可以用于实际应用中。

其中一种比较简单的启发式算法是贪心算法。以下是一种基于贪心算法的二维装箱算法：

1. 将所有箱子按照面积从大到小排序。
2. 依次将每个箱子放入最小的可行矩形中，如果该矩形无法容纳该箱子，则将该矩形旋转90度后重试。
3. 如果所有可行矩形都无法容纳该箱子，则将该箱子放入一个新的矩形中，并将该矩形加入可行矩形列表中。
4. 重复步骤2-3直到所有箱子都被放入矩形中。

以下是一个简单的C++实现：

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

using namespace std;

struct Box {
    double width;
    double height;
    bool rotated;
    double x;
    double y;
};

struct Rectangle {
    double width;
    double height;
    double x;
    double y;
};

bool compare(Box a, Box b) {
    return max(a.width, a.height) > max(b.width, b.height);
}

bool fits(Rectangle r, Box b) {
    return r.width >= b.width && r.height >= b.height;
}

void place(Rectangle& r, Box& b) {
    b.x = r.x;
    b.y = r.y;
    if (b.rotated) {
        swap(b.width, b.height);
    }
    r.x += b.width;
    r.width -= b.width;
    r.height = max(r.height, b.height);
}

void pack(vector<Box>& boxes, double containerWidth, double containerHeight) {
    sort(boxes.begin(), boxes.end(), compare);
    vector<Rectangle> freeRectangles;
    freeRectangles.push_back({containerWidth, containerHeight, 0, 0});
    for (Box& box : boxes) {
        for (Rectangle& rect : freeRectangles) {
            if (fits(rect, box)) {
                place(rect, box);
                box.rotated = false;
                break;
            } else if (fits(rect, {box.height, box.width, true})) {
                place(rect, {box.height, box.width, true, 0, 0});
                box.rotated = true;
                break;
            }
        }
        if (box.x == -1) {
            freeRectangles.push_back({containerWidth, containerHeight - box.height, 0, box.height});
            place(freeRectangles.back(), box);
            box.rotated = false;
        }
    }
}

int main() {
    vector<Box> boxes = {{2, 3}, {4, 1}, {1, 5}, {3, 2}};
    double containerWidth = 6;
    double containerHeight = 6;
    pack(boxes, containerWidth, containerHeight);
    for (Box box : boxes) {
        cout << "Box (" << box.width << ", " << box.height << ") ";
        if (box.rotated) {
            cout << "rotated ";
        }
        cout << "placed at (" << box.x << ", " << box.y << ")" << endl;
    }
    return 0;
}

在上面的实现中，我们使用了一个结构体`Box`来表示每个箱子，它包含宽度、高度、是否旋转以及位置。我们还使用了一个结构体`Rectangle`来表示可行矩形，它包含宽度、高度以及位置。

在`compare`函数中，我们按照最大边长从大到小排序箱子，这是一种启发式方法，旨在使大箱子尽可能先被放入矩形中，以减少剩余空间。

在`fits`函数中，我们检查箱子是否适合放入矩形中。

在`place`函数中，我们将箱子放置在矩形中，并更新矩形的宽度和高度。

在`pack`函数中，我们依次遍历每个箱子，并尝试将其放入可行矩形中。如果矩形无法容纳该箱子，则尝试将矩形旋转90度后再次尝试。如果所有可行矩形都无法容纳该箱子，则将其放入一个新的矩形中，并将该矩形加入可行矩形列表中。

最后，我们在`main`函数中使用一些示例数据来测试算法，并输出每个箱子的位置和是否旋转。