少量约束的几何优化核验记录 ​

返回学习路线。本任务交付一份能够重新执行的记录：点、半平面和抽样 ID 都写明；答案附带小证书；测试程序另外检查完整输入。四页分别解决覆盖圆、抽象违反模型、边界降维和权重抽样，不能用一段“少数约束很重要”的解释代替四个接口。

下载标准库执行器与完整核验结果。直接运行脚本会在同目录生成 JSON；无需安装第三方包。输入只接受整数或 Fraction，不接受浮点 epsilon 判定。主程序含确定种子的重放，自查使用显式 check，开启 Python -O 不会删掉核验。

一、先给圆，再给不能更小的理由 ​

输入依次为

$$(0,0),(4,0),(1,3),(1,1),(4,0),(2,0).$$

输出应为圆心 $(2,1)$、平方半径 $5$。依次检查每个点到中心的平方距离，得到 $5,5,5,1,5,1$，所以六个位置都被覆盖。再提交前三点的系数 $1/4,5/12,1/3$：加权坐标为 $(2,1)$，总权为一。对任意新中心 $z$，这些点的加权平方距离是 $5+\Vert z-(2,1){\Vert }^2$，因此不存在更小的覆盖圆。

执行器种子17的 Welzl 运行产生29个显式栈节点、16次圆内测试、12次违反分支，最大栈深7。这个数字只描述这一条轨迹；期望线性由正文递推证明，不由它推断。完整结果保留每次违反时的前缀长度、被加入的点 ID、强制边界 ID 和旧圆。

再把第三点改成 $(1,1)$，只保留前三个点。应输出中心 $(2,0)$、平方半径 $4$，而三点外接圆的中心是 $(2,-1)$、平方半径 $5$。说明为什么不能在普通子问题中用三点外接圆替代最小圆，也不能在强制边界子问题中随意用直径圆替代外接圆。

迁移时加入重复原点、全部共线点、空输入及分母为 $2^{150}$ 的近共线有理点。输出证书仍须满足精确等式，不能把“非常接近”写成“等于”。

二、把非唯一基全部找出来 ​

令四个输入点是 $(-1,0),(1,0),(0,1),(0,-1)$。枚举16个子集，值取最小圆平方半径，空集值取 $-1$。对每个子集，列出所有包含极小、且保持其值的子集，这才是“全部基”。

完整四点集合恰有两个基：左右相对点、上下相对点。两份基的交为空，所以删除任意一点都不改变完整圆。三点集合却各有一份相对点基，含两个极端元素。不要把完整输入的极端元素数直接拿去替换随机三点子集的极端元素数。

固定抽两点时，六个等可能样本中，两份违反量为零，四份违反量为二，平均为 $4/3$；三点样本的极端元素平均为二。核对

$$\frac{4/3}{4-2}=\frac{2}{2+1}.$$

下一步把四个点的抽样权重改为 $(1,2,1,2)$，改成独立有放回抽取。样本可能重复，不能仍用“六个二元子集等可能”计算。枚举原始抽样位置，按各项权重乘积计算概率，并检查删除重复位置不改变去重集合的值。这是两种抽样接口的实质区别。

最后提交直径反例：$F=\{(-1,0),(1,0)\}$，$G=F\cup \{(0,1)\}$，新点 $(0,-3/2)$。写出值 $4,4,4,25/4$ 对应的四个集合，指出局部性失败的那一个方向。“直径只由两个点决定”不能替代该公理。

三、线性规划要有三类结论 ​

先解最大化 $3x+2y$，约束为 $x\le 4,y\le 3,x\ge 0,y\ge 0,x+y\le 5,2x+y\le 8$。种子7的顺序为 $[4,0,5,3,1,2]$；三次修复依次得到

$$(M,5-M),(4,1),(3,2).$$

最后目标为13。以 $x+y\le 5$、$2x+y\le 8$ 各乘一相加，得到独立上界13；核对返回点取等号。完整日志应同时有6次普通测试、3次修复、3条被扫描的旧约束；每次修复另有四条固定框行，不包含在“旧约束”计数中。

接着提交下面四个边界任务。

原系统与目标	必须返回的结论	可直接核验的证据
$x\le 0,y\ge 100$，最大化$x$	有限最优值0	形式解$(0,M)$，取$M_0=100$，输出$(0,100)$
$x\le 0,x\ge 0$，最大化$y$	目标无界	起点$(0,1)$，方向$(0,1)$
$x\le 0,y\le 0,x+y\ge 1$	不可行	三条原行已矛盾，任意两条仍可行
无约束，目标恒零	有限最优值0	任意实点即可，不能因形式方向非零报无界

第一行尤其要保留 $u=(0,0)$ 不可行这一事实。有限目标只表示 $c\cdot w=0$，不表示可以丢掉 $w$。必须从全部原约束提取足够大的有限 $M_0$；射线起点也按同一方式取得。

迁移任务：将第一行的目标改成 $y$，输出应改为无界；再加入 $y\le 100$，可行域变成一条水平半直线，最大化 $x$ 又得到有限最优点 $(0,100)$。这些变化要求重新检查目标和可行域，不能只复用原状态标签。

四、逐轮核权重，不在候选处提前停止 ​

取128行 $h_i:x\le i$，目标最大化 $x$，用 $\delta =3,r=54$ 和种子194运行加权抽样。四轮记录应为：

1. 总权128，抽中最小 ID 为17，违反总权17；$9\cdot 17>128$，本轮拒绝倍增
2. 总权仍128，最小 ID 为3，违反0、1、2，三权由1变2，总权变131
3. 最小 ID 为1，只违反0，它的当前权重是2；翻倍后总权变133
4. 最小 ID 为0，全部128行都满足，返回最优值0

下载结果保留每轮54个原始抽样 ID。重放时从该轮旧权重算累计票区间，验证去重后的样本、违反集合和总权增量。最后权重应为 $w_0=4,w_1=w_2=2$，其余仍为1。最终解还要满足全部128行，不能只检查54个抽样位置。

把轮数预算设成零，返回必须是未知；把同一随机种子在每轮循环内重置，不能继续声称每轮条件成功概率至少一半。它可能一直重放第一轮的重违反样本而停不下来。

五、成本记录与独立复算 ​

最小圆核心使用显式栈和常数大小的边界 ID；Seidel 核心顺序维护规范最优点，违反时遍历旧前缀。两者在平面精确算术模型下均为期望线性，但全前缀审计、全部一/二/三点枚举、全部形式框顶点枚举都更慢。附件将这些核验工作与算法统计分开。

有限 LP 的额外对偶证书器枚举紧约束法向量对，最坏二次；它用于证明输出最优，不应混入 Seidel 核心的线性时间宣传。加权算法的小枚举内核只处理至多54个不同约束，总循环期望为 $O((n+1)\log (n+2))$ 次基本精确操作，也不能写成完整 Clarkson 混合算法的线性界。

几何数采用 Fraction，计时需要乘上相应位长下的有理运算成本。随机抽样用整数票，权重位长由有效倍增次数控制；伪随机种子用来复现实验，理论期望针对声明的独立抽样模型。

最终记录应包含原输入、三类 LP 状态、圆/LP 小证书、抽样原始 ID、普通与 -O 的一致结果，以及至少一个迁移后改变输出类型的实例。少了其中一项，就还不能区分“程序跑出了一个数”和“这个数具有声明的含义”。