官方题解只能做到 $O(n^2)$？玩的太差了。可以降到确定性的 $O(n\log^4 n)$ 时间、$O(n\log n)$ 空间。关键是：将凸包剥层化为 $O(n)$ 次相邻面搜索和删除，用整数分治建立静态极点查询，再用受限浅切分将删除引起的变化集中到一个递归子集。最后加入有总工作预算的整数剥层，得到完整做法。
以下复杂度在精确算术模型下计算。
我们需要逐层求凸包、删除其顶点，并将各层体积相加。
整数分治与静态极点查询
接下来构造静态凸包。令三维点 $p=(x,y,z)$ 对应运动点 $p(t)=(x,z-ty)$，维护所有运动点的下凸链。对三点 $a,b,c$，定义 $N_{abc}=(x_b-x_a)(z_c-z_a)-(x_c-x_a)(z_b-z_a)$、$D_{abc}=(x_b-x_a)(y_c-y_a)-(x_c-x_a)(y_b-y_a)$。它们的转向值为 $N_{abc}-tD_{abc}$，共线事件的时刻为 $t=N_{abc}/D_{abc}$。
按 $x$ 分治。左右两部分各自的事件已经有序；由于横坐标分离，合并后的下凸链由左链前缀、公切线和右链后缀组成。设公切线端点为 $u,v$，后继变化只有六类：左右链各自的下一个事件，以及 $u,v$ 分别沿所在链向前或向后移动。每次取晚于当前时刻的最早事件，修改链表和公切线。
事件数为什么是线性的？点 $p$ 位于下凸链，当且仅当存在支撑斜率 $\lambda$，使所有 $r\in P$ 满足 $(r_z-p_z)-t(r_y-p_y)-\lambda(r_x-p_x)\ge0$。这些不等式在 $(t,\lambda)$ 平面上定义凸集，其在 $t$ 轴上的投影是区间。因此每个点至多进入、离开下凸链各一次，整条链只有 $O(m)$ 个事件。左右事件各扫描一次，公切线事件也是合并后凸链的事件，故 $T(m)=T(\lfloor m/2\rfloor)+T(\lceil m/2\rceil)+O(m)=O(m\log m)$。对 $z$ 连同其坐标扰动取反再做一遍，即得到另一侧的面。
整数实现直接保存事件对 $(N,D)$，将 $D$ 规范为正，比较两事件时计算 $N_1D_2-N_2D_1$。投影共线和同时事件用一致的符号扰动决定顺序：令第 $i$ 个点的第 $j$ 个坐标变为 $p_{i,j}+\delta^{8^{3i+j}}$。先计算普通整数项，只有普通项为零才展开扰动；每个单项式用参与变量的编号多重集表示；谓词次数和项数均有常数上界，因此每次判断仍只需要常数次精确运算。
六个候选事件按有序三点编号缓存，三点不变便直接复用。同一组三点的排列只会同时改变 $N,D$ 的符号，事件时间相同。入口还可在三个坐标轴中选择重复值最少者作为横轴，通过循环置换 $(x,y,z)\mapsto(y,z,x)$ 或 $(z,x,y)$ 完成；两个变换的行列式均为 $+1$，凸包层和有向体积保持不变。
这段运动过程还能支持极点查询 $\operatorname{ext}_P(q)=\arg\max_{p\in P}p\cdot q$。若 $q_z<0$，取 $t=-q_y/q_z$，则 $p\cdot q=q_xx+q_z(z-ty)$，最大值在时刻 $t$ 的下凸链上。先在事件序列中二分时刻，再在该时刻的凸链上查找目标函数由增转减的位置。$q_z>0$ 使用镜像结构，$q_z=0$ 使用对应的无穷时刻。
用持久化线段树保存每个事件后的活跃点，每个节点记录区间内首尾活跃点。下降时只比较左子树末点与右子树首点的目标值，便能确定最大值所在一侧。因此事件二分与树上下降分别为 $O(\log m)$，一次查询共 $O(\log m)$；$O(m)$ 次事件各复制 $O(\log m)$ 个节点，建库时间、空间均为 $O(m\log m)$。在 $q_z<0$ 的未镜像情形，事件比较可写成 $q_yD+q_zN$ 的符号；镜像坐标 $(x,y,\sigma z)$ 对应查询方向 $(q_x,q_y,\sigma q_z)$，比较相应变为 $q_yD+\sigma q_zN$。链上比较则为 $(a-b)\cdot q$ 的符号，所有几何分支均关于查询方向线性。
局部细分与受限浅切分
将查询方向按绝对值最大的坐标归一化，得到六个 $[-1,1]^2$ 坐标图。点面对应后，极点查询成为图形平面 $h(X,Y,Z)=Z+aX+bY+d=0$ 的下包络查询。定义 $\ell_H(q)=|\{h\in H:h(q)>0\}|$，即严格位于 $q$ 下方的平面数。
参数为 $k$ 的浅切分由 $O(m/k)$ 个向下三角棱柱组成，覆盖 $\ell_H(q)\le k$ 的区域，每个棱柱与 $O(k)$ 个平面相交。相交包括边界接触，相应平面集合称为闭冲突表。
在层次结构中，设旧覆盖区域为 $R$，剔除部分平面后剩下 $H'$，新层的覆盖要求是 $R\cap\{q:\ell_{H'}(q)\le k\}$。这就是受限浅切分。下面给出从旧层构造新层的过程。
先把屋顶的共面三角片合并为真实面，将屋顶稍作抬高并截去各旧顶角。移动量满足两个条件：旧区域仍被包含；每个新顶点的闭冲突表包含于其来源旧顶点的闭冲突表。新顶点位于一条旧边与一个截角面的交点，至多关联三个真实面。全部操作沿旧边和旧面进行，顶点数只增加常数倍。
设新屋顶的规模为 $V$。将其三角面对偶图分成 $O(V/t)$ 组，每组至多含固定的 $t$ 个三角面，组间边数为 $O(V/\sqrt t)$。该对偶图是最大度数为三的平面图。递归使用平面分隔集可得到总边界 $O(V/\sqrt t)$，所以在任何剩余子图中，总存在一个连通集 $S$ 满足 $1\le|S|\le t$、$|\partial S|\le c_0|S|/\sqrt t$。逐次枚举并删除这样的 $S$，再将相邻批次打包即可。每个根只有 $3^{O(t)}$ 个连通候选，删除只影响距离至多 $t$ 的根，故固定 $t$ 时总费用为 $O(V)$。
每组涉及常数个旧棱柱。设其局部冲突集合为 $H_\Delta$、$M=|H_\Delta|$。相邻层参数之比为固定常数，因此 $M=O(k)$。现在将该局部区域细分成常数个四面体，要求每个四面体内部至多被 $k$ 个平面穿过。
对两点 $u,v$，定义有向范围 $W(u,v)=\{h\in H_\Delta:h(u)>0,\ h(v)<0\}$。若 $M\le k$，直接四面体化即可。以下设 $M>k$，取 $\varepsilon=k/(12M)$，构造命中所有大小超过 $\varepsilon M$ 的范围的集合 $E$，再用 $E$ 中的平面切开局部区域并四面体化。
任一结果四面体 $\tau$ 都不被 $E$ 中的平面穿过。设其四个顶点为 $v_1,\ldots,v_4$；穿过 $\tau$ 内部的平面必属于某个 $W(v_i,v_j)$。每个范围都与 $E$ 不交，故大小至多为 $\varepsilon M$。共有 $12$ 个有序顶点对，于是内部穿过数至多为 $12\varepsilon M=k$。
这个常数大小的 $E$ 也可以确定性地构造。对 $s$ 个代表平面，枚举 arrangement 各维面内的一点，得到 $O(s^3)$ 种符号向量；正、负符号集合两两求交，便枚举出全部 $O(s^6)$ 种有向范围。
对有限加权代表集，设范围 $A$ 的权重比例为 $p_A$，希望用 $N$ 个等权代表将所有比例误差压到 $\delta$ 以内。令 $\lambda=\delta/2$、$u_A=\lceil N(p_A+\delta)\rceil$、$l_A=\lfloor N(p_A-\delta)\rfloor$。已选 $j$ 个代表，其中 $c_A$ 个属于 $A$ 时，维护势函数 $\Phi_j=\sum_A\bigl((1+\lambda)^{c_A-u_A}(1+\lambda p_A)^{N-j}+(1-\lambda)^{c_A-l_A}(1-\lambda p_A)^{N-j}\bigr)$；超出 $[0,1]$ 的单侧约束省去。
按原权重选择下一代表时，$\Phi_{j+1}$ 的期望恰好是 $\Phi_j$，所以枚举所有候选并取势函数最小者即可保证不增。取 $N=O(\delta^{-2}\log(|\mathcal R|+1))$ 可使 $\Phi_0<1$，而任一最终误差达到 $\delta$ 都会使对应项至少为 $1$，因此所有范围均满足误差要求。
将输入组织成二进制合并树，在第 $i$ 层分配误差 $\delta_i=\varepsilon/(4i(i+1))$。两个代表块合并后压缩为 $O_\varepsilon(i^5)$ 个代表；单次压缩为 $i^{O_\varepsilon(1)}$，第 $i$ 层至多发生 $M/2^i$ 次，故总费用为 $O_\varepsilon(M\sum_{i\ge1}i^{O_\varepsilon(1)}/2^i)=O_\varepsilon(M)$。总误差小于 $\varepsilon/4$，最终代表数为 $\log^{O_\varepsilon(1)}M$。
范围数的多项式上界给出大小仅依赖 $\varepsilon$ 的命中集存在性。设这个上界为常数 $r_\varepsilon$，在最终代表集上进行深度至多 $r_\varepsilon$ 的搜索：取一个尚未命中的重范围，分支枚举其中被选中的代表。费用为 $\log^{O_\varepsilon(1)}M=O_\varepsilon(M)$。原范围权重若超过 $\varepsilon M$，压缩后仍超过 $3\varepsilon M/4$；命中所有权重超过 $\varepsilon M/2$ 的代表范围，就得到所需的 $E$。
有了局部四面体，把 level 不超过 $5k$ 的顶点列为覆盖目标，level 不超过 $Ck$ 的顶点列为允许候选，枚举最小候选子集，使其向下凸包覆盖所有目标。候选数仅取决于固定参数，所以这一步为常数规模搜索。
若 $\ell_{H'}(q)\le k$ 且 $q\in\tau$，从 $q$ 到 $\tau$ 的任何顶点 $v$，新增下方平面只可能来自内部穿过平面或经过 $q$ 的平面。无四点共面保证后一类至多三个，因此 $\ell_{H'}(v)\le k+k+3\le5k$。四个顶点均成为目标，整个 $\tau$ 随之被覆盖。
还需要保证总选点数为 $O(m/k)$。使用如下几何存在性结论：对于总权为 $W$ 的二维图形直线集或三维图形平面集，以及 $1\le k\le W$，均存在凸浅切分，覆盖加权 level 至多 $k$ 的区域，顶点数为 $O(W/k)$、顶点 level 为 $O(k)$；其中加权 level 定义为 $\sum_h w_h[h(q)>0]$。以下省略这个存在性引理的证明，展开局部选点数如何达到该上界。
给本轮抬高截角后的输入屋顶支撑面赋予足够大的 $\Theta(k)$ 权重，使增广总权仍为 $\widehat m=O(m)$，且增广浅层完全位于输入屋顶下。辅助面在每个局部区域内均不为正，对局部 level 与内部穿过数的贡献为零，因此局部构造只需处理原平面。取覆盖 level 至多 $5k$ 的比较切分，沿分组边界切开；各边界墙上的截线用二维比较切分替换。最后，将每个比较顶点替换为所在局部四面体的四个顶点。这个替换保持覆盖，并只增加至多 $k+3$ 的 level。
取足够大的绝对常数 $g$，可统一令 $C=30g^2+4$、$s=16g$、$A=144s$、$b=CA$、$t=\lceil2048CA/(3g)\rceil^2$。抬高截角后的屋顶至多有 $Am/(8bk)$ 个顶点；每个辅助面赋权 $(C-3)k$ 后有 $\widehat m\le5m/4$。比较顶点替换后的 level 至多为 $30g^2k+k+3\le Ck$，总数至多为 $(2g+2048CA/(3\sqrt t))\widehat m/k\le3g\widehat m/k$。其中第二项来自总量为 $O(V/\sqrt t)$ 的组间墙。
局部选的是最小可行子集，大小不会超过这个比较方案。全局取向下凸包并三角化后，棱柱数至多为 $6g\widehat m/k<sm/k$；每个顶点的闭冲突至多为 $Ck+3$，一个棱柱的闭冲突表包含于其三个顶点冲突表的并集，因而至多为 $(3C+9)k$。规模界与冲突界同时闭合。
第一层从固定方柱开始，令 $k_1=\max(1,\lfloor m/(32C)\rfloor)$，两个顶面三角形放在同一组中；此时没有组间墙：$m>C$ 时用 $\widehat m\le2m$ 和无墙项的比较方案完成计数，$m\le C$ 时四个顶角均为允许候选，直接选取它们即可。以后取 $k_{i+1}=\lfloor k_i/b\rfloor$，直到参数成为常数。常数可通过 $g=1,2,4,\ldots$ 逐组尝试并核对规模、冲突界确定；超过固定的存在性常数后必然成功。
每层的局部冲突总量为 $O(m)$，另需对 $O(m/k_i)$ 个候选建立凸包，所以费用为 $O(m+(m/k_i)\log(m/k_i))$。$k_i$ 几何递减，将所有层相加，得到 $O(m\log m)$ 的层次建库时间。
坏集递归与参数搜索
令一层动态节点建库时包含 $m$ 个平面，切分层数为 $\ell=O(\log m)$。六个坐标图每层至多有 $sm/k_i$ 张闭冲突表，每张至多含 $ck_i$ 个平面，因此全部关联数至多为 $6cs\ell m$。
逐层构造时，将累计关联数超过 $12cs\ell$ 的平面剔除到集合 $B$。由双重计数，$|B|\le(6cs\ell m)/(12cs\ell)=m/2$。剔除发生在保存该层冲突表之前；旧表保留，后续层只处理未剔除集合，故每个平面实际保存的关联数为 $O(\log m)$。这里恰好需要上一节的受限覆盖保证。
对最终未剔除集合建立静态极点结构，对 $B$ 递归建立相同结构。插入一个新平面，直接插入 $B$；查询时比较静态答案与递归答案，已删除的静态答案忽略。
删除平面 $h$ 时，给所有包含 $h$ 的旧冲突表的删除计数加一。第 $i$ 层的表达到 $k_{i+1}$ 次删除，就将表内所有存活平面转入 $B$；末层阈值为 $1$。另设初始全域表，阈值为 $k_1$。
证明查询的覆盖性。设当前答案平面为 $h^*$，查询线与它交于 $q$，且 $h^*\notin B$。若 $q$ 位于最末层棱柱内，那么静态结构要么直接返回它，要么存在已删除的旧平面位于它下方。后一种情形触发末层表，而 $h^*$ 经过 $q$，属于同一张闭冲突表，必已被转入 $B$，矛盾。
若 $q$ 首次在第 $i$ 层失去覆盖，则 $q$ 位于某个第 $i-1$ 层棱柱内，且相对于当时的未剔除集合有 $\ell(q)>k_i$。这些位于 $q$ 下方的平面现在必已全部删除，因此对应表已达到触发阈值，包含 $h^*$ 的存活部分同样已转入 $B$。第一层之前的情形由初始全域表处理。故查询必能找到当前极点。
一张第 $i$ 层表包含 $O(k_i)$ 个平面，触发前发生了 $\Omega(k_{i+1})=\Omega(k_i)$ 次删除，整次转移可以向这些删除均摊。每个平面只在 $O(\log m)$ 张表中，故一次删除在当前递归节点均摊产生 $O(\log m)$ 次递归插入。
当 $|B|\ge3m/4$ 时重建。建库时 $|B|\le m/2$，达到阈值至少需要 $\Omega(m)$ 次加入，足以支付重建费用。处理整层批删时，先标记整批并收集触发表产生的转移，检查是否需要重建，再对子结构执行批删和批插；这样进入删除递归时，子结构规模始终小于 $3m/4$。记建库、插入、删除、查询费用为 $P,I,D,Q$，则 $P(m)\le P(m/2)+O(m\log m)$、$I(m)\le I(3m/4)+O(P(m)/m)$、$D(m)\le D(3m/4)+O(\log m)I(3m/4)+O(\log^2m)$、$Q(m)\le Q(3m/4)+O(\log m)$。
由此得到 $P(m)=O(m\log m)$、$I(m)=O(\log^2m)$、$D(m)=O(\log^4m)$、$Q(m)=O(\log^2m)$。这里 $I,D$ 为均摊费用；递归链上的规模几何缩小，空间同样为 $O(m\log m)$。
最后用极点查询寻找相邻面。设已知朝外三角面为 $(a,b,c_0)$，令 $e=b-a$、$u=e\times(c_0-a)$、$v=e\times u$，让法向量沿 $u+tv$ 转动。由于 $v\cdot(c_0-a)=-\lVert u\rVert^2<0$，旧的第三点进入内侧，下一次接触得到的就是另一侧的面。令 $F(t)=\max_{p\in P}(p-a)\cdot(u+tv)$，第一次接触新顶点的时刻为 $t^*$。因为 $a$ 一直存在，支撑区间内 $F(t)=0$；沿指定方向越过首次接触后，$F(t)>0$。必要时改用相邻参数图 $(v,-u)$，保证 $t^*$ 有限且非负。
模拟在 $t^*+\eta$ 处执行一次极点查询，其中 $\eta>0$ 为无穷小量。查询的每个分支均为方向的线性比较，代入后形如 $\alpha+\beta t$。若 $\beta=0$，直接决定符号；否则令 $r=-\alpha/\beta$。负根位于 $t^*$ 左侧；非负根满足 $F(r)>0\iff r>t^*$，一次普通极点查询即可判断。若 $r>t^*$，比较结果为 $-\operatorname{sgn}\beta$；若 $r\le t^*$，比较结果为 $\operatorname{sgn}\beta$，等号恰好按右侧无穷小处理。方向中的无穷小优先于坐标扰动。
因此，可以逐个决定模拟查询的分支，并得到首次接触顶点 $c$。记 $A=(c-a)\cdot u$、$D=(c-a)\cdot v>0$，新面的朝外法向量直接取 $Du-Av$。一次动态查询包含 $O(\log^2m)$ 个线性比较，每个比较至多调用一次 $O(\log^2m)$ 的普通查询，故相邻面搜索为 $O(\log^4m)$。
起始面也能这样取得。先用两个字典序方向查询找最小 $(x,y)$ 投影处的最低点与最高点；若不同，它们构成竖直凸包边。否则，从支撑 $x$ 平面出发绕该点的竖直线寻找首次接触，得到凸包边，再绕边寻找一个面。沿尚未访问的反向边遍历相邻面，利用凸包面对偶图的连通性枚举整层，最后批量删除该层顶点。
若某层有 $h$ 个顶点，则有 $2h-4$ 个三角面；各层顶点不重复，故全部层合计只有 $O(n)$ 个面和 $O(n)$ 次删除。将面朝外定向，累加 $\det(a,b,c)$ 即得六倍体积，因此总时间为 $O(n\log^4n)$。
预算剥层与复杂度
整数分治可以直接用于前置剥层。令 $L=\lceil\log_2\max(n,2)\rceil$，分配工作预算 $B=nL^3$。当前剩余 $m$ 个点时，若余额至少为 $m$，先扣去 $m$，再建静态凸包并删除其顶点；余额不足，就对完整剩余点集启用上一节的动态结构。
每次静态建包花费 $O(m\log m)$，所有已处理规模满足 $\sum m\le B$，所以前置总费用为 $O(\sum m\log m)\le O(LB)=O(n\log^4n)$。动态阶段具有相同上界。
每轮分治前，还可加入两种 $O(m)$ 的认证。第一种选出候选四面体：取字典序最小点 $a$，依次令 $b=\arg\max_p\|p-a\|^2$、$c=\arg\max_p\|(b-a)\times(p-a)\|^2$、$d=\arg\max_p|\det(b-a,c-a,p-a)|$。若凸包是四面体，这些凸目标函数会选到四个极点；逐面验证其余点严格位于内侧，即可确认整层。
第二种最多枚举固定的 $16$ 个面。一次相邻面查找扫描当前点集；若遍历闭合，直接得到整层；若达到面数上限仍有未处理边，转入整数分治。至多进行常数次扫描，故这两种认证均计入同一轮的 $O(m\log m)$ 费用。
按横坐标及一致的扰动次序只排序一次，之后删除顶点时稳定筛选，下一层仍然有序。原始编号保持不变，删除标记只初始化一次，每轮其余操作均只扫描当前点集。
本题 $n\le3000$ 时，这个预算足以完成全部层。令 $q=\lfloor n/4\rfloor$，每层至少删除四点，于是 $\sum m\le n+(n-4)+\cdots+(n-4(q-1))=q(n-2q+2)\le n(n+4)/8\le nL^3$。
最终，整数分治前置、动态建库、全部相邻面搜索及删除合计为确定性的 $O(n\log^4 n)$ 时间，空间为 $O(n\log n)$。
参考文献
- bulijiojiodibuliduo，The 2024 ICPC Asia East Continent Online Contest (I) 题解，I. Boxes 节。
- Timothy M. Chan，A Minimalist’s Implementation of the 3-d Divide-and-Conquer Convex Hull Algorithm。
- Timothy M. Chan、Konstantinos Tsakalidis，Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings。
- Timothy M. Chan，Dynamic Geometric Data Structures via Shallow Cuttings，第 4 节及附录 A。
- David Haussler、Emo Welzl，Epsilon-nets and simplex range queries。
- Richard J. Lipton、Robert Endre Tarjan，A Separator Theorem for Planar Graphs。
