QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#642373 | #6563. Four Square | enze114514 | TL | 6ms | 3792kb | C++20 | 3.7kb | 2024-10-15 13:37:23 | 2024-10-15 13:37:24 |
Judging History
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