QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#642373#6563. Four Squareenze114514TL 6ms3792kbC++203.7kb2024-10-15 13:37:232024-10-15 13:37:24

Judging History

你现在查看的是最新测评结果

  • [2024-10-15 13:37:24]
  • 评测
  • 测评结果:TL
  • 用时:6ms
  • 内存:3792kb
  • [2024-10-15 13:37:23]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

// 定义一个结构体表示矩形
struct Rectangle {
    int width;
    int height;
};

// 检查两个矩形是否重叠
bool isOverlap(int x1, int y1, int w1, int h1,
               int x2, int y2, int w2, int h2) {
    // 如果一个矩形在另一个的左边
    if (x1 + w1 <= x2 || x2 + w2 <= x1)
        return false;
    // 如果一个矩形在另一个的上边
    if (y1 + h1 <= y2 || y2 + h2 <= y1)
        return false;
    return true;
}

// 尝试将四个矩形放入正方形中
bool canFormSquare(vector<Rectangle> rects, int S) {
    // 存储已放置的矩形的位置和尺寸
    // 每个元素是一个四元组 (x, y, w, h)
    vector<tuple<int, int, int, int>> placed;

    // 递归函数尝试放置第 idx 个矩形
    function<bool(int)> backtrack = [&](int idx) -> bool {
        if (idx == 4) {
            // 所有矩形都已放置,检查是否完全覆盖正方形
            // 由于我们确保没有重叠并且总面积等于 S^2,直接返回 true
            return true;
        }

        // 尝试在正方形的每个可能位置放置当前矩形
        for(int x = 0; x <= S - rects[idx].width; x++) {
            for(int y = 0; y <= S - rects[idx].height; y++) {
                bool canPlace = true;
                // 检查与已放置矩形是否重叠
                for(auto &[px, py, pw, ph] : placed) {
                    if(isOverlap(x, y, rects[idx].width, rects[idx].height, px, py, pw, ph)) {
                        canPlace = false;
                        break;
                    }
                }
                if(canPlace) {
                    // 放置当前矩形
                    placed.emplace_back(x, y, rects[idx].width, rects[idx].height);
                    // 递归放置下一个矩形
                    if(backtrack(idx + 1))
                        return true;
                    // 回溯
                    placed.pop_back();
                }
            }
        }
        return false;
    };

    return backtrack(0);
}

int main(){
    // 读取四个矩形
    vector<Rectangle> rects(4);
    long long total_area = 0;
    for(int i=0;i<4;i++){
        cin >> rects[i].width >> rects[i].height;
        total_area += 1LL * rects[i].width * rects[i].height;
    }

    // 检查总面积是否为完全平方数
    double sqrt_area = sqrt((double)total_area);
    if(abs(sqrt_area - round(sqrt_area)) > 1e-9){
        cout << "0";
        return 0;
    }
    int S = round(sqrt_area);

    // 生成所有可能的旋转组合
    // 每个矩形有两种状态:原始和旋转
    // 总共有 2^4 = 16 种组合
    for(int mask=0; mask<(1<<4); mask++){
        vector<Rectangle> rotated_rects = rects;
        for(int i=0;i<4;i++){
            if(mask & (1<<i)){
                swap(rotated_rects[i].width, rotated_rects[i].height);
            }
        }

        // 生成所有可能的排列
        sort(rotated_rects.begin(), rotated_rects.end(), [&](const Rectangle &a, const Rectangle &b) -> bool{
            if(a.width != b.width)
                return a.width < b.width;
            return a.height < b.height;
        });

        do{
            if(canFormSquare(rotated_rects, S)){
                cout << "1";
                return 0;
            }
        }while(next_permutation(rotated_rects.begin(), rotated_rects.end(), [&](const Rectangle &a, const Rectangle &b) -> bool{
            if(a.width != b.width)
                return a.width < b.width;
            return a.height < b.height;
        }));
    }

    // 如果所有组合都不可行
    cout << "0";
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3792kb

input:

1 1
1 1
1 1
1 1

output:

1

result:

ok single line: '1'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3584kb

input:

3 1
3 3
2 2
3 3

output:

0

result:

ok single line: '0'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3508kb

input:

2 8
2 8
2 8
2 8

output:

1

result:

ok single line: '1'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3580kb

input:

5 3
5 5
3 3
3 5

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3504kb

input:

1 2
4 8
16 32
64 128

output:

0

result:

ok single line: '0'

Test #6:

score: 0
Accepted
time: 6ms
memory: 3584kb

input:

4 4
2 1
4 4
2 1

output:

0

result:

ok single line: '0'

Test #7:

score: -100
Time Limit Exceeded

input:

995 51
559 565
154 536
56 780

output:


result: