JZOJ 2748 「中山市选 2012」最大立方体空间

发表于 | 分类于 | 12

显然可以二分答案。
然而判定貌似更难？

设二分的答案是 \(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
#include <cstdio>
#include <algorithm>
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);
    }
}

Related Issues not found

Please contact @Alpha1022 to initialize the comment