P96 n=50:公开构造边长 365.986166101 精修为 365.986166088,缩短 13 个 1e-9 网格单位。这是有限网格改进,未证明全局最优。 方法:固定每块的 quarter 和 turn。先精确计算全部顶点,将最小 x、y 向下取整到网格,统一平移裁掉边缘空白。再用整数平移 dx、dy 和正整数边长缩减量 d 建立 HiGHS MILP,最大化 d。保留所有顶点包含约束;每对 L 分成两个矩形,对四个跨块矩形对各选当前合法、归一化余量最大的边法向作为分离轴并保持分离。平移及 d 的上限依次为 [2, 10, 100, 1000, 10000],每轮 5 秒、相对 MIP 间隙 0。浮点优化只生成候选,须经两套精确验证才接受。接受的局部步骤:L=2: 365.986166097, L=10: 365.986166089, L=100: 365.986166088。 无需重跑优化器的确定性复现:起始 side=365.986166101;以下各行按短边 k=1..50 排列,格式 [x,y,quarter,turn]: [["169.442509759","189.447157057",0,"-0.043927757"],["359.800960195","234.223801840",0,"-0.009653204"],["168.247214869","188.425136407",0,"-0.018382130"],["142.037800313","87.096108170",0,"-0.004446895"],["357.724703167","232.229130621",0,"-0.008487690"],["164.594340221","185.293032498",0,"0.002873808"],["193.342918590","120.505966520",2,"-0.038478331"],["185.184694399","120.931162112",0,"-0.027453119"],["181.364342672","103.659566528",3,"-0.003629125"],["182.377394481","93.209136606",1,"-0.007181480"],["352.596055041","227.178100176",0,"-0.003382669"],["158.620389958","179.228298547",0,"0.003188465"],["27.999055221","214.999637855",2,"0.004235014"],["14.000000003","214.888095322",0,"0"],["75.114031819","215.465804363",2,"-0.035016091"],["56.996036599","215.478835814",0,"0.004235014"],["341.077844798","348.001650223",2,"-0.027745692"],["322.068225820","347.979228489",0,"0.001024094"],["245.820084071","228.145833586",3,"-0.003948962"],["247.043485956","208.135547316",1,"-0.003948962"],["192.991589258","173.410444801",3,"0.023565121"],["193.981332205","151.456529612",1,"0.000285078"],["238.973615351","165.003998417",3,"0.000285078"],["341.025939093","216.128689697",0,"-0.001117146"],["146.689913134","167.104836757",0,"0.004090014"],["241.988438918","139.005713108",1,"0.000285078"],["165.007439493","56.039096614",3,"-0.000148324"],["165.986166095","28.000000009",1,"0"],["335.490706138","301.002023062",3,"0.001145280"],["335.986166101","270.999421571",1,"0"],["64.000000006","263.495424352",2,"0"],["32.000000003","263.478261896",0,"0"],["67.999800154","329.834458409",2,"0.000280540"],["34.000000006","329.478261899",0,"0"],["35.295190215","164.293196300",3,"0.004235014"],["35.998708681","128.297853909",1,"0.004235014"],["230.974769320","75.999423355",3,"0.000285078"],["231.986166098","38.000000006",1,"0"],["265.029428470","326.986166101",3,"0"],["266.111192450","286.987413622",1,"-0.003948962"],["185.003945085","324.942256755",2,"0.000289023"],["143.003093319","323.986172140",0,"0.000280540"],["182.977264001","238.951243822",2,"0.011497223"],["139.000000009","237.962613324",0,"0"],["92.986166092","46.023314834",2,"0"],["46.986166089","46.000000003",0,"0"],["316.974770948","95.999423353",3,"0.000285078"],["317.986166101","48.000000003",1,"0"],["316.958236423","191.999429532",0,"0.000285078"],["121.886694479","141.886601843",0,"0.004235014"]] 对对应原点加入下列 [dx,dy]×1e-9,保留全部朝向,side 设为 365.986166088: [[-114,-115],[-114,-115],[-114,-115],[-114,-115],[-114,-115],[-114,-115],[-114,-115],[-114,-115],[-114,-115],[-114,-115],[-114,-115],[-114,-115],[94,85],[-3,-115],[-114,-115],[110,-115],[-114,-115],[-114,-115],[90,0],[20,3],[-6,109],[-9,85],[90,6],[-114,-115],[-114,-115],[-11,8],[-114,-115],[-7,-9],[-114,-115],[-13,86],[-6,-115],[-3,109],[-8,105],[-6,109],[110,-115],[-2,-6],[110,-8],[-10,-6],[-114,-13],[-11,-10],[-114,-115],[110,109],[-11,109],[-9,109],[-4,-115],[-1,-3],[95,-6],[-13,-3],[-13,-8],[-6,85]] 精确验证:小数乘 10^9 转为整数,t=turn,以 cos=(1−t²)/(1+t²)、sin=2t/(1+t²) 计算旋转。第一实现将每块分成两矩形,清分母后用整数分离轴检验;第二实现将每块分成三正方形,用有理数多边形裁剪检验交面积为零。全部 50 块的顶点包含和 1225 对块约束均通过;接触允许,正面积重叠拒绝。
P96 · Consecutive L shapes in a square · Discussion