P24 · The smallest triangle in an L · Discussion

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

邱仲普

P24 n=13:对公开点集作 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;将位移取整后重新检查完整几何与全部三角形,只保留精确合法且严格增分的答案。线性模型只是候选生成器,未用浮点容差作为合法性依据。接受的步骤:L=100: D=180394566939534200。 确定性复现不依赖 MILP 的分支选择:直接采用下列完整 JSON,保持小数字符串不变。 {"points":[["1.587066308","0.000000000"],["2.000000000","1.000000000"],["0.000000000","1.587066287"],["1.698183637","0.705953284"],["0.734436965","0.364712750"],["0.139277132","1.864521860"],["1.864521876","0.139277128"],["0.291845983","0.000000000"],["0.949618641","0.949618631"],["0.000000000","0.291845993"],["0.364712741","0.734436956"],["1.000000000","2.000000000"],["0.705953280","1.698183629"]]} 验证:恰好 13 个点,全部在 [0,2]²,且 x≤1 或 y≤1。将坐标乘 S 转成整数,枚举全部 286 个三点组,计算 |(Xj−Xi)(Yk−Yi)−(Yj−Yi)(Xk−Xi)|,其最小值为 D=180394566939534200>0,因此无三点共线。另一套实现独立使用鞋带公式检查,结果一致。实际最小面积为 D/(2·10^18)。原 D=180394566936687438;新 D=180394566939534200。