P24 · The smallest triangle in an L · Discussion

P24 · n = 14 · Solver note / 求解记录

邱仲普

P24 n=14:对公开点集作 1e-9 网格上的局部整数调整,提高最小三角形面积。未证明全局最优。 方法:令 S=10^9、坐标 X=Sx、Y=Sy,目标 D 为全部三点组的最小绝对行列式。固定当前各三点组的行列式符号,在每个点所属的一个凸子区域内限制每个坐标的整数改变量为 [-L,L]。对接近当前最小值的三角形((绝对行列式−D)/S≤20L),线性化行列式,最大化共同增量。使用 scipy.optimize.milp/HiGHS,每次限时 5 秒、相对 MIP gap 0。依次尝试 L=2,10,100,1000,10000,100000;将位移取整后重新检查完整几何与全部三角形,只保留精确合法且严格增分的答案。线性模型只是候选生成器,未用浮点容差作为合法性依据。接受的步骤:L=10: D=151217320317672598。 确定性复现不依赖 MILP 的分支选择:直接采用下列完整 JSON,保持小数字符串不变。 {"points":[["1.791526991","0.000000000"],["2.000000000","0.972204997"],["0.018413500","1.795000914"],["1.791526991","0.725356829"],["1.035886335","0.555976672"],["0.262351222","2.000000000"],["2.000000000","0.105283957"],["0.111376004","0.000000000"],["1.130404633","0.966458546"],["0.000000000","0.523896253"],["0.999999992","2.000000000"],["0.262761510","0.760542184"],["0.756062254","1.795000914"],["0.563719253","0.105283957"]]} 验证:恰好 14 个点,全部在 [0,2]²,且 x≤1 或 y≤1。将坐标乘 S 转成整数,枚举全部 364 个三点组,计算 |(Xj−Xi)(Yk−Yi)−(Yj−Yi)(Xk−Xi)|,其最小值为 D=151217320317672598>0,因此无三点共线。另一套实现独立使用鞋带公式检查,结果一致。实际最小面积为 D/(2·10^18)。原 D=151217320289292869;新 D=151217320317672598。