将固定长宽的背包判定改成上凸包上的资源分配，在题目固定的精度要求下，可以把时间复杂度降至 $O(n+A+k^3)$，其中 $A=\max a_i\le1000$。显式保留相对或绝对误差参数 $\delta$ 时，时间界为 $O(n+A+k^3\log(1/\delta))$。所给代码的交点枚举方法具有 $O(k^6)$ 的最坏时间上界，官方面积二分方法为 $O(k^4\log(V/\varepsilon))$。后两个上界也见于 jiangly 的题解 和 赛事官方题解。这里的改进来自判定算法的结构性质。

设 $m=2k$，约定 $x\ge y$。任何方案只需要 $2m$ 块成品，因此最多使用 $2m$ 根原木。把使用的原木按长度排序后，逐根换成全体中最长的 $2m$ 根，原有切割方式仍然成立。输入长度为至多 $1000$ 的整数，可以用计数数组在 $O(n+A)$ 时间内取得这些原木。

设 $L$ 是能够切出 $m$ 块等长木板的最大长度，$s$ 是能够切出 $2m$ 块等长木板的最大长度。合并各原木的递减序列 $a_i,a_i/2,a_i/3,\ldots$，第 $m$ 大和第 $2m$ 大的数分别就是 $L$ 和 $s$，用堆取出前 $2m$ 项即可。切出 $m$ 块长度 $L$ 的木板后，各自二等分，说明 $L/2\le s$。正方形给出面积下界 $s^2$，任意长边则满足 $x\le L$。

固定长宽时，可以消去背包。

给定 $x,y$，第 $i$ 根原木切出 $p$ 块长为 $x$ 的木板后，最多还能切出 $f_i(p)=\lfloor(a_i-px)/y\rfloor$ 块长为 $y$ 的木板，定义域为整数 $0\le p\le\min(m,\lfloor a_i/x\rfloor)$。需要判断，在 $\sum p_i=m$ 的条件下，$\sum f_i(p_i)$ 是否至少为 $m$。

把每根原木对应的点 $(p,f_i(p))$ 按横坐标排列，取上凸包，记其上边界函数为 $g_i$。所有原始点都位于直线 $z=(a_i-px)/y$ 的下方，凸包也位于该直线下方。因此，对于每个整数 $p$，有 $f_i(p)\le g_i(p)<f_i(p)+1$，即 $\lfloor g_i(p)\rfloor=f_i(p)$。实现把 $f_i$ 截断至 $m$，该性质仍然成立，因为截断后的连续上界 $\min(m,(a_i-px)/y)$ 也是凹函数。

暂时允许在凸包边上使用分数长度。凸包的一条边记为 $(d_x,d_y)$：横向增加 $d_x$ 块长木板，纵向损失 $d_y$ 块短木板。每根原木内部的损失率 $d_y/d_x$ 单调递增，所以把所有边按损失率从小到大取用，直到横向总量为 $m$，就是连续问题的最优解。同一根原木的边会按合法的先后顺序取用。

关键在于整数化。贪心过程中最多有一条边只使用一部分，其他原木都停在横坐标为整数的凸包顶点。总横向长度 $m$ 是整数，因此最后那条边使用的横向长度也是整数，所得每个 $p_i$ 都合法。只有这条部分边所在原木的纵坐标可能带有小数，对其向下取整就得到真实的 $f_i(p_i)$。于是，离散最优值恰好等于连续最优值向下取整。

这一证明允许合并凸包边，却仍然保留每根原木的切割限制。设初始短木板总数为 $B=\sum f_i(0)$，完整取用的边损失总数为 $D$，最后一条边取用横向长度 $t$，最大短木板数量就是 $B-D-\lceil t d_y/d_x\rceil$。这些运算全部使用整数。

面积判定只需要检查 $O(k^2)$ 个长宽组合。

检查面积 $R>s^2$ 是否可行。在双曲线 $xy=R$ 上，只需考虑 $\sqrt R\le x\le L$。此时 $x/y=x^2/R<4$，而且 $\sum\lfloor a_i/\sqrt R\rfloor<2m$，否则正方形面积至少为 $R$，与 $R>s^2$ 矛盾。因此，任意一次固定长宽判定中，所有原木的横坐标点数合计都是 $O(m)$；凸包构造和凸包边总数也都是 $O(m)$。

对于一种固定的整数切割方案，每根原木提供约束 $px+qR/x\le a_i$。在 $x$ 轴上，每个约束对应一个区间，因此该方案的全部约束也对应一个区间。假设面积可行，取某个方案首次可行的位置。正方形位置不可行，所以此处必有一个约束刚刚成立，即 $px+qR/x=a_i$。需要枚举的是约束的进入位置，也就是较小的根 $x=2qR/(a_i+\sqrt{a_i^2-4pqR})$。该表达式避免两个接近的数相减，$p=0$ 时也适用。

进入位置满足 $q>p$。令 $c_i=\lfloor a_i/\sqrt R\rfloor$，则只需枚举 $0\le p\le\min(m,\lfloor c_i/2\rfloor)$，以及 $\max(p+1,c_i+1-p)\le q\le m$。还可以令 $t=\min(L,a_i/(2p))$，把 $q$ 的上限缩小为 $\lfloor(a_it-pt^2)/R\rfloor$；当 $p=0$ 时取 $t=L$。代码同时检查根的范围和判别式。

进入位置还满足 $q\le a_iL/R<2a_i/\sqrt R<2(c_i+1)$。因此，每根原木产生 $O((c_i+1)^2)$ 个候选。又因为 $\sum(c_i+1)=O(m)$，候选总数为 $O(m^2)$。相同长度的原木只需生成一次候选，它们在切割判定中仍然分别保留。

凸包边还可以在线性时间内选择。相邻整数横坐标间的损失至多为 $\lceil x/y\rceil\le4$，凸包边的平均损失率也在 $[0,4]$ 中，且分母 $d_x\le m$。两个不同损失率的差至少为 $1/m^2$，因此整数键 $h=\lfloor d_y m^2/d_x\rfloor$ 严格保持损失率的顺序。取大于 $2m$ 的最小二次幂 $b$，键值小于 $b^2$，只需两位基数。先按高位累计横向长度和损失，找到包含第 $m$ 个横向单位的桶；再在这个桶内按低位选择。完整桶的损失是整数，最后一桶内所有边的损失率相同，可以合并计算部分损失。整个选择过程为 $O(m)$。边数至多 $12$ 时，代码使用固定规模的插入排序。

于是，纯粹的固定长宽判定为 $O(m)$，一次面积判定为 $O(m^3)$。代码预先计算整数键，耗时和空间都是 $O(m^2)$。

实际实现还利用成功判定产生的整数切割方案提高面积下界。固定每根原木的两种切割数量后，可行区域由 $p_ix+q_iy\le a_i$ 构成。按斜率建立这些直线的下包络，在每一段上检查抛物线 $x(a_i-p_ix)/q_i$ 的顶点和端点，就能求出该分配的最大面积。这个步骤仅在一次面积判定成功时执行一次，额外耗时为 $O(m\log m)$，保持一次面积判定的 $O(m^3)$ 上界。

外层每轮先检查比当前答案大 $2\times10^{-10}\max(1,\mathrm{ans})$ 的面积。如果判定失败，当前答案满足题目精度。如果判定成功，就利用整数方案提高下界，再检查剩余区间的中点。每轮至多执行两次面积判定，并把区间长度至少减半。面积上界取 $\min(L^2,(\sum a_i/(2m))^2)$，其中求和只包含保留的原木。

初始下界为 $s^2$，上界至多为 $L^2\le4s^2$，所以初始区间长度至多为 $3s^2$。允许的终止尺度 $\delta\max(1,\mathrm{ans})$ 至少为 $\delta s^2$，二分轮数为 $O(\log(1/\delta))$。总时间复杂度为 $O(n+A+k^3\log(1/\delta))$，空间复杂度为 $O(A+k^2)$；固定题目精度后，时间界简写为 $O(n+A+k^3)$。这给出了较交点枚举和官方背包方案更低的可证明上界；全问题的渐近最优性仍需要匹配的下界证明。

浮点数仅用于尺寸、根和面积。凸包转向、斜率键、数量和损失均通过整数计算。每次提高答案时，都根据具体整数分配的原始约束重新计算面积。

Submission： https://qoj.ac/submission/2998864