P96 n=38:公开构造边长 243.725256076 精修为 243.725255098,缩短 978 个 1e-9 网格单位。这是有限网格改进,未证明全局最优。 方法:固定每块的 quarter 和 turn。先精确计算全部顶点,将最小 x、y 向下取整到网格,统一平移裁掉边缘空白。再用整数平移 dx、dy 和正整数边长缩减量 d 建立 HiGHS MILP,最大化 d。保留所有顶点包含约束;每对 L 分成两个矩形,对四个跨块矩形对各选当前合法、归一化余量最大的边法向作为分离轴并保持分离。平移及 d 的上限依次为 [2, 10, 100, 1000, 10000],每轮 5 秒、相对 MIP 间隙 0。浮点优化只生成候选,须经两套精确验证才接受。接受的局部步骤:L=2: 243.725256074, L=10: 243.725256064, L=100: 243.725255964, L=1000: 243.725255100, L=10000: 243.725255098。 无需重跑优化器的确定性复现:起始 side=243.725256076;以下各行按短边 k=1..38 排列,格式 [x,y,quarter,turn]: [["73.530194344","74.010001971",0,"-0.000099347"],["72.527553769","73.010202572",0,"-0.000389585"],["186.483545499","102.196738096",3,"0.002237774"],["70.501475008","70.762265229",0,"-0.000363094"],["186.545955422","97.194584373",1,"-0.001606741"],["65.028338190","89.987179258",3,"-0.000521179"],["65.547354740","82.966953310",1,"0.001103130"],["179.959298735","125.342563642",3,"-0.005764952"],["66.485285861","66.736988017",0,"0.001396020"],["180.079267933","115.182334614",1,"0.003260388"],["203.547799944","116.241503798",3,"0.000504607"],["203.564961521","104.227873569",1,"-0.000400626"],["229.569744222","120.270229290",3,"0.000008025"],["229.578020127","106.261404720",1,"-0.000036174"],["94.017000427","31.985563594",3,"0.006448712"],["95.136278711","16.000000000",1,"0.000000000"],["93.653818919","82.985121323",3,"0.006449030"],["94.346918745","64.992563680",1,"0.006448712"],["57.441240810","57.458137453",0,"0.004035097"],["146.279251959","223.055809930",2,"-0.000352615"],["124.573598037","222.727002782",0,"0.006449030"],["80.291866087","146.463955477",3,"0.003106434"],["80.858470688","122.823406832",1,"0.006449030"],["77.910129062","219.579420517",3,"0.001986991"],["78.944210631","193.697544593",1,"0.006449030"],["26.363965031","217.428557860",3,"0.000386569"],["26.997754622","189.211046386",1,"0.006449030"],["28.406762662","134.224645254",3,"0.006449030"],["28.999055666","105.230209854",1,"0.004035902"],["212.483404122","62.198907940",3,"0.000672472"],["212.725256076","31.158214698",1,"0.000000000"],["136.256251883","169.873283897",3,"0.006449030"],["136.681870481","136.876028392",1,"0.006449030"],["146.286740046","69.994344100",3,"0.006449030"],["146.725256076","35.000000341",1,"0.000000000"],["205.963354024","207.725256066",3,"0.000000000"],["206.725256076","170.725256066",1,"0.000000000"],["38.595190442","38.305424967",0,"0.004035097"]] 对对应原点加入下列 [dx,dy]×1e-9,保留全部朝向,side 设为 243.725255098: [[10725,11108],[-11495,-11112],[-11495,-11112],[-11495,11088],[-11495,-11112],[-11495,-11112],[-11495,-11112],[-11495,-11112],[10705,-11112],[-11495,-11112],[-11495,-11112],[-11495,-11112],[-11495,-11112],[-11495,-11112],[-9482,-261],[10729,0],[-9519,-647],[-492,-175],[63,37],[-11495,-11112],[607,-978],[-11495,-11112],[-380,-734],[-11495,-11112],[-289,-8860],[-11495,-11112],[-387,-1246],[-9495,-1095],[-383,-396],[-11495,-11112],[-978,-11112],[-662,-994],[-981,-668],[-751,-327],[-978,-341],[-11495,-968],[-978,-968],[327,0]] 精确验证:小数乘 10^9 转为整数,t=turn,以 cos=(1−t²)/(1+t²)、sin=2t/(1+t²) 计算旋转。第一实现将每块分成两矩形,清分母后用整数分离轴检验;第二实现将每块分成三正方形,用有理数多边形裁剪检验交面积为零。全部 38 块的顶点包含和 703 对块约束均通过;接触允许,正面积重叠拒绝。
P96 · Consecutive L shapes in a square · Discussion