浮点数开根

pufanyi

随笔

发布于：Feb 23, 2019

给你讲个鬼故事。

有一只 神犇 叫 Wzp，模拟赛时出了一道 计算几何题 ， 精度开到了 1e-13。

题目大意就是给你一个 $\Delta ABC$ 和$n(n\le 1000)$个向量，你可以在其中选至多 $k$ 个作用在 $A$ 上，使最终得到的三角形周长最长。特别的，这个三角形可以退化成一条线，其实只要算 $AB+BC+AC$ 就可以了。

其中所有给出的数据（包括向量的$x, y$）都是整数。

正解在这里就不说了 我才不会告诉你是因为我不会做这道题 ，重点是那个细节，也就是1e-13 的精度应该怎么整。

重点就是那个sqrt，这玩意考场上测了一下（用long double）精度大概只有$10^{-8}\sim 10^{-9}$，直接悲惨爆 0……

有一个很妙的trick，我们设需要计算$s=\sqrt{x}$，我们设 $s$ 的整数部分是$a$，小数部分是$b$，我们有：

$$\begin{aligned} x&=(a+b)^2\\ &=a^2+b^2+2ab\\ &=a^2+b(a+b)+ab\\ &=a^2+bs+ab\\ &=a^2+b(s+a) \end{aligned}$$

所以：

$$\begin{aligned} b=\frac{x-a^2}{s+a} \end{aligned}$$

其中的 s 直接调用 sqrt() 即可。

这样我们就可以用一个 long long 和一个double（甚至不用long double）来表示浮点数，精度也会高很多。

更新于：Jul 2, 2023

数学

模拟赛