P96 n=48:公开构造边长 343.764616306 精修为 343.764616265,缩短 41 个 1e-9 网格单位。这是有限网格改进,未证明全局最优。 方法:固定每块的 quarter 和 turn。先精确计算全部顶点,将最小 x、y 向下取整到网格,统一平移裁掉边缘空白。再用整数平移 dx、dy 和正整数边长缩减量 d 建立 HiGHS MILP,最大化 d。保留所有顶点包含约束;每对 L 分成两个矩形,对四个跨块矩形对各选当前合法、归一化余量最大的边法向作为分离轴并保持分离。平移及 d 的上限依次为 [2, 10, 100, 1000, 10000],每轮 5 秒、相对 MIP 间隙 0。浮点优化只生成候选,须经两套精确验证才接受。接受的局部步骤:L=1000: 343.764616303, L=10000: 343.764616265。 无需重跑优化器的确定性复现:起始 side=343.764616306;以下各行按短边 k=1..48 排列,格式 [x,y,quarter,turn]: [["187.610230598","216.052424610",0,"0.001065175"],["339.506670690","265.652519626",0,"-0.000097049"],["186.533910417","214.996636065",0,"0.000203079"],["97.517576555","221.074215145",0,"0.000092665"],["337.499846481","263.651985152",0,"-0.000451177"],["182.692790645","211.978289671",0,"0.000199314"],["221.181414366","111.358442495",3,"-0.000289340"],["221.327418292","103.351651499",1,"0.000027982"],["20.977386207","235.224657293",2,"0.001034408"],["10.428976780","235.022103058",0,"0.004767490"],["332.295619176","258.637373848",0,"-0.001085513"],["176.220686174","205.811656628",0,"-0.000619264"],["120.000000512","108.073476309",2,"-0.000000018"],["106.000000084","101.888635892",0,"-0.000000003"],["31.978372529","326.638177131",2,"0.018967446"],["16.000000000","326.068261439",0,"0.000000000"],["84.017675016","326.612264403",2,"-0.000874703"],["65.034784547","325.777563152",0,"0.018967446"],["209.115132983","159.092925680",3,"-0.016958589"],["208.623040026","139.098113826",1,"-0.016958589"],["21.709303968","289.037877727",3,"0.001471847"],["22.017006484","267.038712455",1,"0.000729265"],["320.722595020","246.572041402",0,"-0.006218739"],["164.081539262","193.151828438",0,"-0.000049687"],["210.081084621","318.764616306",3,"0.000000000"],["210.764615786","292.764616306",1,"-0.000000010"],["71.865628527","281.004338491",3,"0.018966261"],["72.890955842","253.041637455",1,"0.000772566"],["219.147940110","237.764616138",3,"-0.000000010"],["219.114597857","207.781866778",1,"-0.016958589"],["243.245083775","64.319051694",3,"-0.000470152"],["243.764611806","32.000131627",1,"-0.000001125"],["308.726584887","67.989661412",3,"0.004979778"],["309.764616306","34.000000000",1,"0.000000000"],["308.764616306","308.050154781",2,"-0.000000000"],["272.764616306","307.764616306",0,"0.000000000"],["306.117431552","138.945114847",2,"-0.008824289"],["267.350325314","138.841251301",0,"0.001544821"],["171.944444480","80.149069271",3,"-0.001870367"],["171.794815803","40.149348975",1,"-0.001870365"],["142.175035777","302.560215374",3,"-0.001333548"],["142.875796644","259.770466430",1,"0.008368116"],["88.159332483","44.111399739",2,"-0.001397360"],["44.010729773","44.000000000",0,"0.000000000"],["45.916964792","179.999871700",3,"0.000772566"],["46.000000000","134.000000000",1,"0.000000000"],["296.781098315","223.536495075",0,"-0.013242782"],["140.000002339","169.073483840",0,"0.000000107"]] 对对应原点加入下列 [dx,dy]×1e-9,保留全部朝向,side 设为 343.764616265: [[-11000,-11000],[-11000,-11000],[-11000,-11000],[-41,-42],[-11000,-11000],[-11000,-11000],[-11000,-11000],[-11000,-11000],[-11000,-11000],[-9000,-162],[-11000,-11000],[-11000,-11000],[0,-68],[0,-9000],[-423,10982],[0,-165],[-11000,-11000],[-4,-41],[-10932,322],[-246,-90],[-8833,-191],[10870,-133],[-11000,-11000],[-11000,-11000],[-11000,-41],[-41,-41],[-40,-42],[-40,-42],[-39,-41],[-40,-47],[-11000,-11000],[-41,-11000],[-99,-1],[-41,0],[-41,-11000],[-41,-68],[-41,72],[-45,92],[0,-40],[0,-40],[-11000,9000],[-40,-72],[-11000,-11000],[-11000,0],[9562,15],[0,0],[-41,-68],[6,-68]] 精确验证:小数乘 10^9 转为整数,t=turn,以 cos=(1−t²)/(1+t²)、sin=2t/(1+t²) 计算旋转。第一实现将每块分成两矩形,清分母后用整数分离轴检验;第二实现将每块分成三正方形,用有理数多边形裁剪检验交面积为零。全部 48 块的顶点包含和 1128 对块约束均通过;接触允许,正面积重叠拒绝。
P96 · Consecutive L shapes in a square · Discussion