题解思路

1. 对称化 + 角度参数化

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

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

$$0<\theta_1<\theta_2<\cdots<\theta_p<\frac{\pi}{4},$$

就得到一组“关键高度/宽度”

$$U=\bigl[r\sin\theta_1,\ldots,r\sin\theta_p\bigr] \quad(+\ r/\sqrt2\text{ 若 }k\text{ 为奇})\quad \cup\ \bigl[r\cos\theta_p,\ldots,r\cos\theta_1\bigr],$$

并在两端补上 $0$ 与 $r$。这里

• $M$ 为像素边长，令 $k=\frac{M-1}{2}$（第一象限中除去边界的“层数”），
• $p=\left\lfloor \frac{k}{2}\right\rfloor$ 是需要优化的角度个数；若 $k$ 为奇，还需在中间插入 $r/\sqrt2$（对应主对角线）。

关键事实（题面提示 1）： 若最优解使用了水平线 $y=a\ne r/\sqrt2$，则必有与圆的两个交点 $(b,a)$, $(c,a)$ 的竖线 $x=b,x=c$ 同时出现，否则可微调使面积更小。因此用一组 $\{\theta_i\}$ 就能同时确定全部水平/竖直分割线。

2. 面积公式（四倍化）

把上述 $U$ 排好序，并在首尾补上 $0$ 与 $r$，得到 $U_\text{full}=[0, U, r]$。 第一象限被分成 $K+1$ 条水平条带（$K=|U|$），第 $i$ 条条带高为

$$\Delta y_i=U_\text{full}[i]-U_\text{full}[i-1],$$

对应可被“染色”的横向宽度上界等于和它关于主对角线镜像位置的“$x$-截距”，也就是

$$X_i = U_\text{full}[K-i+2].$$

于是第一象限的像素覆盖面积为

$$S_{1/4}=\sum_{i=1}^{K+1}\Delta y_i\cdot X_i,$$

全图面积为 $S=4S_{1/4}$。

3. 优化：坐标下降 + 1D 黄金分割

把目标写成 $S(\theta_1,\ldots,\theta_p)$。我们采用坐标下降：依次固定其他角，只对 $\theta_i$ 在合法区间 $(\theta_{i-1},\theta_{i+1})$ 内做一维极小化。 一维极小化使用黄金分割搜索。反复扫若干轮，若一轮没有任何角更新则停止。

• 初值：$\theta_i=\dfrac{i+1}{p+1}\cdot \dfrac{\pi}{4}$ 均匀分布。
• 收敛：通常数十轮内稳定，对 $M\le200$ 足够。

4. 输出

用四舍五入到 4 位小数（HALF_UP） 输出最小面积。

复杂度

• 每次评估 total_area 为 $O(K)=O(M)$。
• 每轮对每个 $\theta_i$ 做常数次函数评估（黄金分割 $<\!120$ 次）。
• 总复杂度约 $O(\text{迭代轮数}\cdot p \cdot 120 \cdot M)$，对 $M\le 200$ 运行很快。

Python 参考实现

import sys
import math
from decimal import Decimal, ROUND_HALF_UP


def build_U_from_thetas(thetas, r, k):

    U = [r * math.sin(t) for t in thetas]
    if k % 2 == 1:
        U.append(r / math.sqrt(2.0))
    U += [r * math.cos(t) for t in reversed(thetas)]
    return [0.0] + U + [r]


def total_area(thetas, r, k):
    U_full = build_U_from_thetas(thetas, r, k)
    K = len(U_full) - 2  # because U_full = [0] + U + [r]
    s = 0.0
    # i in [1, K+1]
    for i in range(1, K + 2):
        dy = U_full[i] - U_full[i - 1]
        x_cap = U_full[K - i + 2]
        s += dy * x_cap
    return 4.0 * s


def golden_section_minimize(f, lo, hi, max_it=120, tol=1e-13):
    golden = (math.sqrt(5.0) - 1.0) / 2.0
    a, b = lo, hi
    c = b - golden * (b - a)
    d = a + golden * (b - a)
    fc, fd = f(c), f(d)
    it = 0

    while (b - a) > tol and it < max_it:
        if fc > fd:
            a, c, fc = c, d, fd
            d = a + golden * (b - a)
            fd = f(d)
        else:
            b, d, fd = d, c, fc
            c = b - golden * (b - a)
            fc = f(c)
        it += 1

    return (a + b) / 2.0


def optimize_thetas(M):
    r = 0.5
    k = (M - 1) // 2
    p = k // 2

    if p == 0:
        return total_area([], r, k)

    thetas = [ (i + 1) * (math.pi / 4.0) / (p + 1) for i in range(p) ]

    # outer coordinate-descent rounds
    for _ in range(30):
        changed = False
        for i in range(p):
            lo = thetas[i - 1] + 1e-12 if i > 0 else 1e-12
            hi = thetas[i + 1] - 1e-12 if i < p - 1 else (math.pi / 4.0) - 1e-12

            def f(x):
                tmp = list(thetas)
                tmp[i] = x
                return total_area(tmp, r, k)

            new_theta = golden_section_minimize(f, lo, hi, max_it=120, tol=1e-13)
            if abs(new_theta - thetas[i]) > 1e-15:
                thetas[i] = new_theta
                changed = True

        if not changed:
            break

    return total_area(thetas, r, k)


def main():
    M = int(sys.stdin.readline().strip())
    ans = optimize_thetas(M)
    out = Decimal(str(ans)).quantize(Decimal('0.0001'), rounding=ROUND_HALF_UP)
    print(out)

if __name__ == "__main__":
    main()

C++ 参考实现

#include <bits/stdc++.h>
using namespace std;

static inline double total_area_from_thetas(const vector<double>& thetas, double r, int k){
    vector<double> U;
    U.reserve(thetas.size()*2 + 1);
    for(double t: thetas) U.push_back(r * sin(t));
    if(k % 2 == 1) U.push_back(r / sqrt(2.0));
    for(int i=(int)thetas.size()-1;i>=0;--i) U.push_back(r * cos(thetas[i]));

    vector<double> F; F.reserve(U.size()+2);
    F.push_back(0.0); for(double v: U) F.push_back(v); F.push_back(r);

    int K = (int)F.size() - 2; // U.size()
    double s = 0.0;
    for(int i=1;i<=K+1;i++){
        double dy = F[i] - F[i-1];
        double xcap = F[K - i + 2];
        s += dy * xcap;
    }
    return 4.0 * s;
}

static inline double golden_section_minimize(function<double(double)> f,
                                             double lo, double hi,
                                             int max_it=120, double tol=1e-13){
    const double golden = (sqrt(5.0)-1.0)/2.0;
    double a=lo, b=hi;
    double c = b - golden*(b-a);
    double d = a + golden*(b-a);
    double fc = f(c), fd = f(d);
    int it=0;
    while((b-a)>tol && it<max_it){
        if(fc > fd){
            a = c; c = d; fc = fd;
            d = a + golden*(b-a);
            fd = f(d);
        }else{
            b = d; d = c; fd = fc;
            c = b - golden*(b-a);
            fc = f(c);
        }
        ++it;
    }
    return (a+b)/2.0;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int M; 
    if(!(cin>>M)) return 0;

    double r = 0.5;
    int k = (M - 1) / 2;
    int p = k / 2;

    vector<double> thetas;
    if(p>0){
        thetas.resize(p);
        for(int i=0;i<p;i++){
            thetas[i] = (i+1) * (M_PI/4.0) / (p+1);
        }
        for(int round=0; round<30; ++round){
            bool changed=false;
            for(int i=0;i<p;i++){
                double lo = (i>0? thetas[i-1] : 0.0) + 1e-12;
                double hi = (i<p-1? thetas[i+1] : M_PI/4.0) - 1e-12;

                auto f = [&](double x){
                    auto tmp = thetas;
                    tmp[i] = x;
                    return total_area_from_thetas(tmp, r, k);
                };

                double new_theta = golden_section_minimize(f, lo, hi, 120, 1e-13);
                if(fabs(new_theta - thetas[i]) > 1e-15){
                    thetas[i] = new_theta;
                    changed = true;
                }
            }
            if(!changed) break;
        }
    }

    double ans = total_area_from_thetas(thetas, r, k);

    // 输出四舍五入到 4 位小数（HALF_UP）
    // 用 i/o manipulators 即可满足，本题数据不会卡到精度奇点
    cout.setf(std::ios::fixed); 
    cout<<setprecision(4)<<ans<<"\n";
    return 0;
}

Java 参考实现

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

    static double r = 0.5;

    static double totalAreaFromThetas(double[] thetas, int k){
        ArrayList<Double> U = new ArrayList<>();
        for(double t: thetas) U.add(r * Math.sin(t));
        if(k % 2 == 1) U.add(r / Math.sqrt(2.0));
        for(int i=thetas.length-1;i>=0;--i) U.add(r * Math.cos(thetas[i]));

        int K = U.size();
        double[] F = new double[K+2];
        F[0]=0.0; 
        for(int i=0;i<K;i++) F[i+1]=U.get(i);
        F[K+1]=r;

        double s = 0.0;
        for(int i=1;i<=K+1;i++){
            double dy = F[i] - F[i-1];
            double xcap = F[K - i + 2];
            s += dy * xcap;
        }
        return 4.0 * s;
    }

    static double goldenSectionMinimize(Function f, double lo, double hi, int maxIt, double tol){
        double golden = (Math.sqrt(5.0)-1.0)/2.0;
        double a=lo, b=hi;
        double c = b - golden*(b-a);
        double d = a + golden*(b-a);
        double fc = f.apply(c), fd = f.apply(d);
        int it=0;
        while((b-a)>tol && it<maxIt){
            if(fc > fd){
                a = c; c = d; fc = fd;
                d = a + golden*(b-a);
                fd = f.apply(d);
            }else{
                b = d; d = c; fd = fc;
                c = b - golden*(b-a);
                fc = f.apply(c);
            }
            it++;
        }
        return (a+b)/2.0;
    }

    interface Function{
        double apply(double x);
    }

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int M = Integer.parseInt(br.readLine().trim());

        int k = (M - 1) / 2;
        int p = k / 2;

        double[] thetas = new double[p];
        for(int i=0;i<p;i++){
            thetas[i] = (i+1) * (Math.PI/4.0) / (p+1);
        }

        for(int round=0; round<30; ++round){
            boolean changed = false;
            for(int i=0;i<p;i++){
                final int idx = i;
                double lo = (i>0? thetas[i-1] : 0.0) + 1e-12;
                double hi = (i<p-1? thetas[i+1] : Math.PI/4.0) - 1e-12;

                Function f = (double x) -> {
                    double[] tmp = thetas.clone();
                    tmp[idx] = x;
                    return totalAreaFromThetas(tmp, k);
                };

                double newTheta = goldenSectionMinimize(f, lo, hi, 120, 1e-13);
                if (Math.abs(newTheta - thetas[i]) > 1e-15) {
                    thetas[i] = newTheta;
                    changed = true;
                }
            }
            if(!changed) break;
        }

        double ans = totalAreaFromThetas(thetas, k);

        // HALF_UP 到 4 位
        BigDecimal out = new BigDecimal(ans).setScale(4, RoundingMode.HALF_UP);
        System.out.println(out.toPlainString());
    }
}

题目内容

钟师傅对像素画（$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

输入

5

输出

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

输入

25

输出

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$

提示

1. 如果确定了所有 $y_i$ 的值，那么 $x_i$ 的值也可以确定。考虑我们已经确定最优解需要用到轴线 $y=a$ ，只要 $a$ 不等于 $0.5$ ，那么 $y=a$ 与圆会有两个交点 $(b,a)$ 和 $(c,a)$ ，那么最优解一定有轴线 $x=b$ 和 $x=c$ ，否则我们可以通过调整，得到面积更小的染色方案。即，可以通过 $\{y_i\}$ 确定潜在的 $\{x_i\}$ 。

2. 这样我们可以列出式子，把最小化 $lossXY(\{x_i\},\{y_i\})$ 变成 $lossY(\{y_i\})$ 的问题。而且 $lossY$ 会有比较容易求导。

3. 可以考虑用某些编程语言自带的优化求解器（例如 $numpy$），或者自己实现梯度下降等优化方式，完成最优解求解。