P96 n=45:公开构造边长 312.976102746 精修为 312.976101161,缩短 1585 个 1e-9 网格单位。这是有限网格改进,未证明全局最优。 方法:固定每块的 quarter 和 turn。先精确计算全部顶点,将最小 x、y 向下取整到网格,统一平移裁掉边缘空白。再用整数平移 dx、dy 和正整数边长缩减量 d 建立 HiGHS MILP,最大化 d。保留所有顶点包含约束;每对 L 分成两个矩形,对四个跨块矩形对各选当前合法、归一化余量最大的边法向作为分离轴并保持分离。平移及 d 的上限依次为 [2, 10, 100, 1000, 10000],每轮 5 秒、相对 MIP 间隙 0。浮点优化只生成候选,须经两套精确验证才接受。接受的局部步骤:L=2: 312.976102744, L=10: 312.976102734, L=100: 312.976102634, L=1000: 312.976101634, L=10000: 312.976101161。 无需重跑优化器的确定性复现:起始 side=312.976102746;以下各行按短边 k=1..45 排列,格式 [x,y,quarter,turn]: [["86.793666321","126.276700616",0,"-0.000467487"],["85.792675689","125.272863002",0,"0.000510648"],["167.315362926","279.026528411",0,"0.000273590"],["164.963384397","270.527642792",2,"-0.000259015"],["83.766931729","123.269553020",0,"-0.001274537"],["158.885725882","270.478550916",0,"-0.000619162"],["159.426737328","191.339657706",3,"0.000504989"],["159.435139054","183.339372964",1,"0.000176852"],["177.480535729","195.100532820",3,"0.002292836"],["177.552068314","185.097784286",1,"-0.000677192"],["78.507484387","118.130385882",0,"-0.003955639"],["70.917106911","26.162498206",3,"0.000377883"],["71.065624230","13.138957082",1,"-0.000006583"],["157.243613597","298.976098130",2,"0.000000000"],["141.907869629","297.894694257",0,"0.012802168"],["110.931590720","296.571518436",2,"0.012802168"],["93.941122201","295.981674280",0,"0.012802168"],["38.032291187","19.025659944",2,"0.000179027"],["19.030589181","19.003230934",0,"-0.000081073"],["166.380982679","155.112796424",3,"-0.001044632"],["166.976102152","133.945102116",1,"0.000000000"],["67.295149427","107.185289638",0,"-0.003809504"],["219.358525904","288.376767344",2,"-0.014089945"],["195.347097072","288.309447009",0,"-0.014089945"],["52.009933069","287.479004436",2,"0.010043848"],["26.019648620","286.976110176",0,"0.000378001"],["117.048036414","157.682679878",3,"0.000378001"],["117.897795341","129.687927232",1,"-0.008698621"],["211.954186935","234.637712327",2,"0.000378001"],["181.954389493","234.358024329",0,"0.000378001"],["118.959204206","248.652878667",3,"0.016258872"],["119.967732069","216.684904625",1,"0.000378001"],["123.503024423","68.581171765",3,"-0.008698621"],["122.911562947","34.586316576",1,"-0.008698621"],["277.003896463","274.977562540",3,"-0.014089945"],["276.976102746","237.991461788",1,"0.000000000"],["194.435677647","75.995670115",3,"0.004006091"],["194.976102516","38.000000166",1,"0.000000000"],["272.460162784","79.994415193",3,"0.005412301"],["272.976102516","40.000000198",1,"0.000000000"],["271.976102746","160.991461018",2,"0.000000000"],["229.976102746","160.991461018",0,"0.000000000"],["43.537719748","217.989334156",3,"0.000378001"],["43.999988037","173.989670662",1,"0.000378001"],["45.000000640","84.956418267",0,"0.000000000"]] 对对应原点加入下列 [dx,dy]×1e-9,保留全部朝向,side 设为 312.976101161: [[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-1001,3031],[-1151,8888],[-842,9075],[-367,-1587],[-11112,-11112],[-11112,-11112],[-11112,-11112],[-1003,-662],[-11112,-11112],[-1233,11112],[-1382,-1585],[0,-1615],[0,-1585],[-9605,-985],[-516,-699],[-1542,-1585],[-1222,-10012],[-578,-1593],[-607,-1565],[-637,-88],[-635,0],[-1585,-1388],[-1585,-1019],[-9148,-229],[-1355,-166],[-9139,484],[-1355,-198],[-1597,-249],[-1597,-249],[-8732,-1591],[-607,-1189],[-640,-304]] 精确验证:小数乘 10^9 转为整数,t=turn,以 cos=(1−t²)/(1+t²)、sin=2t/(1+t²) 计算旋转。第一实现将每块分成两矩形,清分母后用整数分离轴检验;第二实现将每块分成三正方形,用有理数多边形裁剪检验交面积为零。全部 45 块的顶点包含和 990 对块约束均通过;接触允许,正面积重叠拒绝。
P96 · Consecutive L shapes in a square · Discussion