显然可以二分答案。
然而判定貌似更难？
设二分的答案是 \(mid\)。
考虑把箱子的长宽高全部减去 \(mid\)，所有盒子的后左下角三个坐标也都减去 \(mid\)。
这样子就只需要找一个没有被覆盖的点即可（它就是一个可行空间的后左下角）。
找没有被覆盖的点，显然可以扫描线。
（或许叫做扫描面？）
类比二维平面上的扫描线，我们可以把每个箱子的上下面作为边界，按照高度排序并扫描。
为了防止超出这个空间，我们可以一开始在维护的数据结构上全部加一，并把箱子的下表面加入扫描线（贡献为 \(-1\)）。
类似地，把箱子的上表面加入扫描线（贡献为 \(1\)），并在做完扫描线后把整个平面 \(-1\)。
然后考虑使用什么数据结构。
二维的话，可以试试树套树。
然鹅此题要支持矩形修改矩形查询最值，标记不好打，所以先枪毙。
考虑二维线段树，然鹅我不会（大雾）。
然后——\(n\) 才 \(1000\)，不如数组套线段树！
复杂度 \(O(n^2 \log^2 n)\)。
以及注意计算几何题一些处理边界的 \(\pm 1\) 操作。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
using namespace std;
const int N = 1e3;
const int C = 1e3;
int T;
int n,L,W,H;
int l,r,mid,ans;
struct box
{
int x,y,z,X,Y,Z;
} b[N + 5];
struct note
{
int x1,y1,x2,y2,z,w;
inline bool operator<(const note &o) const
{
return z < o.z || (z == o.z && w > o.w);
}
} a[(N << 1) + 10];
int tot;
struct node
{
int min,add;
int ls,rs;
} seg[N * C * 10 + 10];
int rt[C + 5];
inline void push(int p)
{
if(!seg[p].add)
{
if(seg[p].ls)
seg[seg[p].ls].min += seg[p].add,seg[seg[p].ls].add += seg[p].add;
if(seg[p].rs)
seg[seg[p].rs].min += seg[p].add,seg[seg[p].rs].add += seg[p].add;
seg[p].add = 0;
}
}
void update(int l,int r,int k,int &p,int tl,int tr)
{
static int tot = 0;
if(!p)
p = ++tot;
if(l <= tl && tr <= r)
{
seg[p].min += k,seg[p].add += k;
return ;
}
int mid = tl + tr >> 1;
if(l <= mid)
update(l,r,k,seg[p].ls,tl,mid);
if(r > mid)
update(l,r,k,seg[p].rs,mid + 1,tr);
seg[p].min = min(seg[seg[p].ls].min,seg[seg[p].rs].min) + seg[p].add;
}
int query(int l,int r,int p,int tl,int tr)
{
if(!p || (l <= tl && tr <= r))
return seg[p].min;
int mid = tl + tr >> 1;
int ret = 0x3f3f3f3f;
if(l <= mid)
ret = min(ret,query(l,r,seg[p].ls,tl,mid));
if(r > mid)
ret = min(ret,query(l,r,seg[p].rs,mid + 1,tr));
return ret + seg[p].add;
}
int c[C + 5][C + 5];
inline void update(int x1,int y1,int x2,int y2,int k)
{
for(register int i = x1;i <= x2;++i)
update(y1,y2,k,rt[i],0,C);
}
inline int query(int x1,int y1,int x2,int y2)
{
int ret = 0x3f3f3f3f;
for(register int i = x1;i <= x2;++i)
ret = min(ret,query(y1,y2,rt[i],0,C));
return ret;
}
bool check()
{
if(L < mid || W < mid || H < mid)
return 0;
tot = 0;
bool ret = 0;
L -= mid,W -= mid,H -= mid;
for(register int i = 1;i <= n;++i)
a[++tot] = (note){b[i].x - mid,b[i].y - mid,b[i].X,b[i].Y,b[i].z - mid + 1,1},
a[++tot] = (note){b[i].x - mid,b[i].y - mid,b[i].X,b[i].Y,b[i].Z,-1};
a[++tot] = (note){-1,-1,L + 1,W + 1,0,-1};
a[++tot] = (note){-1,-1,L + 1,W + 1,H + 1,1};
sort(a + 1,a + tot + 1);
update(0,0,L,W,1);
for(register int i = 1;i <= tot;++i)
{
update(max(a[i].x1 + 1,0),max(a[i].y1 + 1,0),min(a[i].x2 - 1,L),min(a[i].y2 - 1,W),a[i].w);
if(!query(0,0,L,W))
ret = 1;
}
update(0,0,L,W,-1);
L += mid,W += mid,H += mid;
return ret;
}
int main()
{
scanf("%d",&T);
for(register int cas = 1;cas <= T;++cas)
{
scanf("%d%d%d%d",&n,&L,&W,&H);
for(register int i = 1;i <= n;++i)
scanf("%d%d%d%d%d%d",&b[i].x,&b[i].y,&b[i].z,&b[i].X,&b[i].Y,&b[i].Z);
ans = l = 0,r = min(L,min(W,H));
while(l <= r)
{
mid = l + r >> 1;
if(check())
l = mid + 1,ans = mid;
else
r = mid - 1;
}
printf("Case %d: %d\n",cas,ans);
}
}