RainAir
My OI Blog
RainAir
TCO2017 Round 1A PolygonRotation

题目描述

We have a convex polygon in the XY plane. The vertices of the polygon are the points (x[0], y[0]), (x[1], y[1]), … in clockwise order. You are given the vector s x and y.

In order to make the implementation simpler the polygon and its representation satisfy some additional constraints. Please read the Constraints section carefully.

A three-dimensional solid is obtained by rotating this polygon around the Y axis. Compute and return the volume of the resulting solid.

题目大意

你得到了一个二维凸包,这个凸包满足以下奇怪性质:
1. 在 y 轴上恰好有两个点
2. 设在 y 轴上的两个点分别是 $(0,y_{min})$ 与 $(0,y_{max})$,其中 $y_max > y_min$,那么其 他所有点的 $y$ 坐标都介于 $[y_{min},y_{max}]$ 之间
3. 没有重点,没有三点共线
你需要输出将这个凸包绕 $y$ 轴旋转得到的立体图形的体积。
绝对误差或相对误差小于 $10^{-9}$ 即为正确。

解题报告

又一道计算几何题。。。。。
首先要知道有一个神奇的东西,用来算函数图像绕某定轴旋转后的立体面积的:Disc Intergration
(为了不用科学上网,我把和这题有关的内容搬过来):
“If the function to be revolved is a function of x, the following integral represents the volume of the solid of revolution:
$$\pi \int_{a}^{b} R(x)^2 dx$$
where $R(x)$ is the distance between the function and the axis of rotation. This works only if the axis of rotation is horizontal (example: $y = 3$ or some other constant).”
我们考虑按照 y 轴切成很多片,对每一片分别算完答案后再拼起来。
每一小片可以近似的看成一个去掉头的圆锥或者是圆柱,我们找到与当前切割线 $y=y0$ 相交的绝对值最大的那一条,然后累加它的体积。如果切得足够多精度误差就会小于 $10^{-9}$ 了吧。
核心思想就是这样。。。然后我们放一下代码并解释一些东西。

一些 Simple 的问题

统计答案时的代码相信有些人看不懂,所以我略微解释一下:
为什么奇数位乘 4,而偶数位乘 2 呢?首先那个积分我们是不能直接算的(我们也不会算),于是我们可以将它近似展开:
$$
\int_{a}^b f(x)dx = \sum_{i = 2}^n \frac{\Delta x}{3}(y_{n-2}+4y_{n-1}+y_n)
$$
推导大概如下:
https://blog.aor.sd.cn/wp-content/uploads/2019/06/0FFF7A0BB5F84B0A2A6B6162E4BB07C1-1024x503.jpg
然后写一下每一个 y 对答案的贡献,就得到了最开始和最后贡献是 1 倍,其余奇数位 4 倍偶数位 2 倍了。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/601
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 NOIP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

  • https://secure.gravatar.com/avatar/6d6908271cd6c8777c0a604354a711f5?s=80&d=mm&r=g
    Qingyu

    Orz wyh又爆切神仙题了

    3月前回复
  • https://secure.gravatar.com/avatar/2cf2fb45ac2dd0f024d4ce27aec91f4a?s=80&d=mm&r=g
    Logey

    tql

    3月前回复

RainAir

TCO2017 Round 1A PolygonRotation
题目描述 We have a convex polygon in the XY plane. The vertices of the polygon are the points (x[0], y[0]), (x[1], y[1]), ... in clockwise order. You are given the vector s …
扫描二维码继续阅读
2019-06-09
标签
近期评论