本题是所谓的Cheeger问题（求$\mathbb R^n$中有界开集$\Omega$的Borel子集F，使得F的周长与Lebesgue测度之比最小）。
如果不考虑这些整点处的桩，则最优解是把正方形的四角都替换为圆弧，可以参考此文。
其中圆弧的半径是正方形的$1/(2 + \sqrt{\pi})$时取到最优比例$500/(2 + \sqrt{\pi})\approx 132.53972607$。
本题中的离散解显然应该尽可能接近这一连续解，以下代码改写自官方论坛，利用对称性将正方形八等分（水平、垂直、对角），并递推计算其中一块的比例。
最终结果是$132.52756426$。
注：因需用cache装饰器作记忆化搜索，以下为Python 3代码。
注2：理解本题的背景所需要的前置知识一般在数学系本科高年级或研究生低年级的《实分析》课程中讲授。
import math
from functools import *
def heron(a,b,c):
s=0.5*(a+b+c)
v=s*(s-a)*(s-b)*(s-c)
return math.sqrt(v) if v>=0 else 0
def dist(x,y,x2,y2):
a=math.sqrt(x*x+y*y)
b=math.sqrt(x2*x2+y2*y2)
c=math.sqrt((x-x2)*(x-x2)+(y-y2)*(y-y2))
A=heron(a,b,c)
return A-r*c,A,c
r=132.53972607
@cache
def check(x,y):
bests,besta,bestp=dist(x,y,y,x)
bests*=0.5
besta*=0.5
bestp*=0.5
for y2 in range(y+1,min(y+15,251)):
for x2 in range(y2,min(x+15,251)):
s,a,p=dist(x,y,x2,y2)
s2,a2,p2=check(x2,y2)
if s+s2>bests:
bests,besta,bestp=s+s2,a+a2,p+p2
return bests,besta,bestp
s,a,p=check(250,0)
print(f'{a/p:.8f}')
|
