P96 n=48:公开构造边长 343.764618356 精修为 343.764616306,缩短 2050 个 1e-9 网格单位。这是有限网格改进,未证明全局最优。 方法:固定每块的 quarter 和 turn。先精确计算全部顶点,将最小 x、y 向下取整到网格,统一平移裁掉边缘空白。再用整数平移 dx、dy 和正整数边长缩减量 d 建立 HiGHS MILP,最大化 d。保留所有顶点包含约束;每对 L 分成两个矩形,对四个跨块矩形对各选当前合法、归一化余量最大的边法向作为分离轴并保持分离。平移及 d 的上限依次为 [2, 10, 100, 1000, 10000],每轮 5 秒、相对 MIP 间隙 0。浮点优化只生成候选,须经两套精确验证才接受。接受的局部步骤:L=2: 343.764618354, L=10: 343.764618344, L=100: 343.764618244, L=1000: 343.764617244, L=10000: 343.764616306。 无需重跑优化器的确定性复现:起始 side=343.764618356;以下各行按短边 k=1..48 排列,格式 [x,y,quarter,turn]: [["187.610241710","216.052435935",0,"0.001065175"],["339.506681802","265.652530951",0,"-0.000097049"],["186.533921529","214.996647390",0,"0.000203079"],["97.517576911","221.074216719",0,"0.000092665"],["337.499857593","263.651996477",0,"-0.000451177"],["182.692801757","211.978300996",0,"0.000199314"],["221.181425478","111.358453820",3,"-0.000289340"],["221.327429404","103.351662824",1,"0.000027982"],["20.977397319","235.224668618",2,"0.001034408"],["10.428985892","235.022105082",0,"0.004767490"],["332.295630288","258.637385173",0,"-0.001085513"],["176.220697286","205.811667953",0,"-0.000619264"],["120.000001260","108.073476752",2,"-0.000000018"],["106.000000683","101.888645017",0,"-0.000000003"],["31.978372295","326.638186232",2,"0.018967446"],["16.000000000","326.068264359",0,"0.000000000"],["84.017686128","326.612275728",2,"-0.000874703"],["65.034784749","325.777565202",0,"0.018967446"],["209.115141895","159.092926343",3,"-0.016958589"],["208.623041400","139.098114545",1,"-0.016958589"],["21.709313783","289.037880308",3,"0.001471847"],["22.017004469","267.038714782",1,"0.000729265"],["320.722606132","246.572052727",0,"-0.006218739"],["164.081550374","193.151839763",0,"-0.000049687"],["210.081095733","318.764618356",3,"0.000000000"],["210.764617238","292.764618356",1,"-0.000000010"],["71.865628613","281.004340537",3,"0.018966261"],["72.890955945","253.041639334",1,"0.000772566"],["219.147941621","237.764617845",3,"-0.000000010"],["219.114599392","207.781868189",1,"-0.016958589"],["243.245094887","64.319063019",3,"-0.000470152"],["243.764613564","32.000140756",1,"-0.000001125"],["308.726586726","67.989661626",3,"0.004979778"],["309.764618064","34.000000213",1,"0.000000000"],["308.764618356","308.050166106",2,"-0.000000000"],["272.764618356","307.764617889",0,"0.000000000"],["306.117433510","138.945115756",2,"-0.008824289"],["267.350327272","138.841252202",0,"0.001544821"],["171.944445732","80.149069469",3,"-0.001870367"],["171.794817062","40.149349173",1,"-0.001870365"],["142.175046889","302.560204499",3,"-0.001333548"],["142.875797443","259.770468406",1,"0.008368116"],["88.159343595","44.111411064",2,"-0.001397360"],["44.010740885","44.000000880",0,"0.000000000"],["45.916953921","179.999873023",3,"0.000772566"],["46.000000000","134.000000880",1,"0.000000000"],["296.781099854","223.536496658",0,"-0.013242782"],["140.000003282","169.073484912",0,"0.000000107"]] 对对应原点加入下列 [dx,dy]×1e-9,保留全部朝向,side 设为 343.764616306: [[-11112,-11325],[-11112,-11325],[-11112,-11325],[-356,-1574],[-11112,-11325],[-11112,-11325],[-11112,-11325],[-11112,-11325],[-11112,-11325],[-9112,-2024],[-11112,-11325],[-11112,-11325],[-748,-443],[-599,-9125],[234,-9101],[0,-2920],[-11112,-11325],[-202,-2050],[-8912,-663],[-1374,-719],[-9815,-2581],[2015,-2327],[-11112,-11325],[-11112,-11325],[-11112,-2050],[-1452,-2050],[-86,-2046],[-103,-1879],[-1511,-1707],[-1535,-1411],[-11112,-11325],[-1758,-9129],[-1839,-214],[-1758,-213],[-2050,-11325],[-2050,-1583],[-1958,-909],[-1958,-901],[-1252,-198],[-1259,-198],[-11112,10875],[-799,-1976],[-11112,-11325],[-11112,-880],[10871,-1323],[0,-880],[-1539,-1583],[-943,-1072]] 精确验证:小数乘 10^9 转为整数,t=turn,以 cos=(1−t²)/(1+t²)、sin=2t/(1+t²) 计算旋转。第一实现将每块分成两矩形,清分母后用整数分离轴检验;第二实现将每块分成三正方形,用有理数多边形裁剪检验交面积为零。全部 48 块的顶点包含和 1128 对块约束均通过;接触允许,正面积重叠拒绝。
P96 · Consecutive L shapes in a square · Discussion