自动搬运

查看原文

来自洛谷，原作者为

	iuyi hello

搬运于2025-08-24 22:40:39，当前版本为作者最后更新于2024-04-23 08:58:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

因为圆盘与地面平行，所以在地面的投影也是圆形，半径不变，圆心坐标的计算公式题目已经给了。

问题转化为给定矩形区域和若干圆，求矩形区域中没有被圆覆盖的面积。

多个圆重叠的部分直接计算比较困难。

注意到只需要输出两位小数，于是考虑使用自适应辛普森积分。

将 $x$ 轴视为积分区间，函数值为从 $(x,0)$ 到 $(x,b)$ 内没有被覆盖的长度。

计算函数值时先求出所有圆在直线上覆盖的区间端点（如果有的话），然后按顺序扫过所有点，记录当前位置被覆盖了几次，累加被覆盖次数为 $0$ 的区间。

python 可以使用绘图库，非常方便。

from math import sqrt, sin, cos, pi

# import matplotlib.pyplot as plt
# import numpy as np

eps = 1e-7

a, b = map(int, input().split())
g = float(input()) / 180 * pi
n = int(input())
cirs = [tuple(map(float, input().split())) for _ in range(n)]

cotg = cos(g) / sin(g)
# x, y, r
cirs = [(x + z * cotg, y, r) for x, y, z, r, in cirs]

# fig, ax = plt.subplots()
# ax.set_xlim(0, a)
# ax.set_ylim(0, b)
# ax.set_box_aspect(b / a)
#
# for x, y, r in cirs:
#     an = np.linspace(0, 2 * np.pi, 100)
#     plt.plot(x + r * np.cos(an), y + r * np.sin(an))

# def showline(func):
#     def wrapper(fi):
#         plt.plot([fi, fi], [0, b])
#         return func(fi)
#
#     return wrapper

callf = 0

# @showline
def f(fi: float) -> float:
    global callf
    callf += 1
    l = [(0, 0), (b, 0)]
    for x, y, r, in cirs:
        if abs(fi - x) < r:
            d = sqrt(r ** 2 - (fi - x) ** 2)
            if y + d > 0 and y - d < b:
                l.append((y - d, 1))
                l.append((y + d, -1))
    l.sort()
    ret: float = 0
    fills: int = 0
    last = l[0][0]
    for p, c in l:
        if fills == 0:
            ret += p - last
        fills += c
        last = p
    return ret

# print(f(1))
# plt.show()

def simpson(l: float, r: float) -> float:
    mid = (l + r) / 2
    return (r - l) / 6 * (f(l) + f(r) + 4 * f(mid))

def integrate(l: float, r: float, step: int) -> float:
    mid = (l + r) / 2
    s = simpson(l, mid) + simpson(mid, r)
    if step <= 0 and abs(s - simpson(l, r)) < eps:
        return s
    return integrate(l, mid, step - 1) + integrate(mid, r, step - 1)

print(f'{integrate(0, a, 5):.2f}')
# print(callf)