题解思路

1. 对称化 + 角度参数化

圆心在 $(\tfrac12,\tfrac12)$ ，半径 $r=\tfrac12$ 。最优网格一定关于水平 $[0,r]\times[0,r]$ 里描述边界，再用对称扩展到整圆。

设我们在第一象限里取若干条水平线 $y=r\sin\theta$ 与竖直线 $x=r\cos\theta$ （ $\theta\in(0,\tfrac\pi4)$ ）。给定一组严格递增的角度

P4442.第3题-须从规矩出方圆

1000ms

Tried: 153

Accepted: 18

Difficulty: 9

所属公司 : 华为

算法与标签>数学

题目内容

钟师傅对像素画（ $Pixel$ $Art$ ）有独特的品味理解，他最近沉迷于用胶带拼图形贴画面海报，但是竟然后发现，像素画，每个 $pixel$ 的长宽都是固定的。

一种像素圆的画法是，将每个像素块看成一个独立正方形，如果正方形和圆的交集面积大于 $10^{-10}$ ，则涂黑像素块。例如左图就是一个典型 $25\times25$ 像素圆。可以看到每个像素的行宽和列宽是相同的，它占用原图的 $533/(25*25)=0.8528=85.28\%$ 范围。而 $\pi/4\approx78.5398\%$ 。

钟师傅喜欢精确的圆，因此他决定设计一种新的像素屏，专门为画圆而生，每行的间距和列间距不需要一样，为此它可以画出更精确的圆。

具体来说，如果给定像素是 $M\times M$ ，那么钟师傅需要给出 $M-1$ 个行宽变量和 $M-1$ 个列高变量，记出 $\{x_i\},\{y_i\}$

固定 $x_0=y_0=0,x_{M-1}=y_{M-1}=1$ ，然后以 $x=x_i,y=y_i$ 作 $2M-2$ 条直线，将 $(0,0)-(1,1)$ 这个正方形划分成 $M\times M$ 个小矩形。每个矩形被涂色当且仅当这个矩形和以 $(0.5,0.5)$ 为圆心，半径为 $0.5$ 的单位圆交集面积 $>10^{-10}$ 。

例如 $M=25,x_i=y_i=\frac{i}{25}$ ，对应的像素逼近圆就是左图。

如果更精细地设置 $x$ 和 $y$ 的间距，就能得到更好的逼近，目标是在 $M$ 固定的前提下，把染色块的面积量最小化。右图是一种更优的设定方案，具体数值参考样例。

钟师傅为了找到 $M=25$ 的划分已经耗尽了全部心力，他希望你帮忙找到其他 $M$ 的最优划分方案，特别的，为了方便计算，本题的 $M$ 都是奇数。

输入描述

一行一个整数， $M$ ，输入保证 $5 \le M \le 200$ ，并且 $M$ 是奇数。

输出描述

输出最优染色面积，精确到小数点后 $4$ 位。

例如 $M=25$ 的最优答案约为 $0.810767848$ ，那么四舍五入后，你应该输出 $0.8108$

样例1

输入

输出

0.8784

说明

$M=5$ 的最优划分见下图：

面积约为 $0.8784148931$

划分方案：

$x_1 = y_1 = 0.08824681693923937$

$x_2 = y_2 = 0.2163464855861515$

$x_3 = y_3 = 0.7836535144138486$

$x_4 = y_4 = 0.911753183060766$

样例2

输入

输出

0.8108

说明

最优分布：

$x_1 = y_1 = 0.014219468994025153$

$x_2 = y_2 = 0.032278207527408176$

$x_3 = y_3 = 0.053248663959798335$

$x_4 = y_4 = 0.07678775198872612$

$x_5 = y_5 = 0.10277889747804814$

$x_6 = y_6 = 0.1312450507717095$

$x_7 = y_7 = 0.1623318383092049$

$x_8 = y_8 = 0.1963301205070792$

$x_9 = y_9 = 0.23374562325992837$

$x_{10} = y_{10} = 0.27547112225909104$

$x_{11} = y_{11} = 0.3232619881117089$

$x_{12} = y_{12} = 0.381605423707194$

$x_{13} = y_{13} = 0.618394576292806$

$x_{14} = y_{14} = 0.6767380118882911$

$x_{15} = y_{15} = 0.7245288777409089$

$x_{16} = y_{16} = 0.7662543767400716$

$x_{17} = y_{17} = 0.8036698794929208$

$x_{18} = y_{18} = 0.8376681616690795$

$x_{19} = y_{19} = 0.8687549492282904$

$x_{20} = y_{20} = 0.897221105219519$

$x_{21} = y_{21} = 0.9232122480112739$

$x_{22} = y_{22} = 0.94675136660420166$

$x_{23} = y_{23} = 0.9677217924725918$

$x_{24} = y_{24} = 0.9857805310059748$

提示

如果确定了所有 $y_i$ 的值，那么 $x_i$ 的值也可以确定。考虑我们已经确定最优解需要用到轴线 $y=a$ ，只要 $a$ 不等于 $0.5$ ，那么 $y=a$ 与圆会有两个交点 $(b,a)$ 和 $(c,a)$ ，那么最优解一定有轴线 $x=b$ 和 $x=c$ ，否则我们可以通过调整，得到面积更小的染色方案。即，可以通过 $\{y_i\}$ 确定潜在的 $\{x_i\}$ 。
这样我们可以列出式子，把最小化 $lossXY(\{x_i\},\{y_i\})$ 变成 $lossY(\{y_i\})$ 的问题。而且 $lossY$ 会有比较容易求导。
可以考虑用某些编程语言自带的优化求解器（例如 $numpy$ ），或者自己实现梯度下降等优化方式，完成最优解求解。

输入

预期输出（选填）

题解思路

1. 对称化 + 角度参数化

P4442.第3题-须从规矩出方圆

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About