P96 n=39:公开构造边长 252.965666104 精修为 252.965666079,缩短 25 个 1e-9 网格单位。这是有限网格改进,未证明全局最优。 方法:固定每块的 quarter 和 turn。先精确计算全部顶点,将最小 x、y 向下取整到网格,统一平移裁掉边缘空白。再用整数平移 dx、dy 和正整数边长缩减量 d 建立 HiGHS MILP,最大化 d。保留所有顶点包含约束;每对 L 分成两个矩形,对四个跨块矩形对各选当前合法、归一化余量最大的边法向作为分离轴并保持分离。平移及 d 的上限依次为 [2, 10, 100, 1000, 10000, 100000],每轮 5 秒、相对 MIP 间隙 0。浮点优化只生成候选,须经两套精确验证才接受。接受的局部步骤:L=2: 252.965666092, L=10: 252.965666082, L=100: 252.965666079。 无需重跑优化器的确定性复现:起始 side=252.965666104;以下各行按短边 k=1..39 排列,格式 [x,y,quarter,turn]: [["75.070290406","143.028081849",0,"-0.014177759"],["74.042021413","142.015755489",0,"-0.003908431"],["80.949482499","189.247392612",0,"-0.011151712"],["198.685751077","236.029171046",3,"-0.004112156"],["72.026392315","140.011625474",0,"-0.001430317"],["199.708708328","230.011024727",1,"-0.002489947"],["186.880411586","231.841670111",1,"-0.062794376"],["187.671602973","240.729923046",3,"-0.042300050"],["67.012093690","135.008356951",0,"-0.000452977"],["88.915476586","176.638206647",3,"0.050303845"],["89.923747708","165.734534950",1,"0.002480532"],["190.999085396","212.026090630",3,"-0.001318410"],["191.965666094","198.994448841",1,"0.000000000"],["130.879315589","174.792350478",2,"0.002480532"],["115.903583622","169.863472596",0,"0.002480532"],["236.965666098","164.039967782",2,"0.000000000"],["219.965889176","164.045089668",0,"-0.002561500"],["184.985503376","167.963372801",2,"-0.002561500"],["58.003941187","126.003941191",0,"-0.000103726"],["164.985765821","168.065832124",0,"-0.002561500"],["123.926859266","44.000000008",3,"0.000000000"],["123.926859270","22.000000004",1,"0.000000000"],["228.722481101","229.176566798",3,"-0.001182771"],["228.965666098","205.122159405",1,"0.000000000"],["52.557516275","171.987563960",2,"-0.011151712"],["26.000000004","172.000000012",0,"0.000000000"],["27.525432832","224.975230035",0,"-0.009827758"],["56.009838101","224.917802193",2,"-0.000855445"],["108.454720187","125.825976606",3,"0.002480532"],["108.940925290","95.844851745",1,"-0.014270360"],["148.003023826","220.856216057",2,"-0.000855445"],["116.003070656","220.910964492",0,"-0.000855445"],["68.985281374","33.970569330",2,"-0.014931834"],["34.000000004","34.000000004",0,"0.000000000"],["217.965287680","36.000378428",2,"0.000005406"],["181.926859274","36.000000004",0,"0.000000000"],["215.858164987","109.999854368",2,"-0.000992008"],["177.784756463","110.000000008",0,"0.000000000"],["39.000000004","107.000000008",0,"0.000000000"]] 对对应原点加入下列 [dx,dy]×1e-9,保留全部朝向,side 设为 252.965666079: [[108,-116],[104,108],[-5,108],[103,104],[-14,-18],[107,107],[106,107],[102,108],[-10,-15],[5,107],[1,103],[103,87],[-16,83],[-5,-17],[-2,103],[-19,104],[-15,87],[-12,84],[-7,-11],[-8,87],[108,-8],[104,-4],[108,108],[-19,104],[-8,-16],[-4,-12],[-97,-14],[-5,-19],[105,103],[101,-14],[-13,-23],[-9,-20],[-6,-7],[-4,-4],[-116,104],[104,-4],[104,-10],[103,-8],[-4,-8]] 精确验证:小数乘 10^9 转为整数,t=turn,以 cos=(1−t²)/(1+t²)、sin=2t/(1+t²) 计算旋转。第一实现将每块分成两矩形,清分母后用整数分离轴检验;第二实现将每块分成三正方形,用有理数多边形裁剪检验交面积为零。全部 39 块的顶点包含和 741 对块约束均通过;接触允许,正面积重叠拒绝。
P96 · Consecutive L shapes in a square · Discussion