# 浮点数开根

Author: Fanyi Pu

Published: 2019-02-23

Canonical: <https://pufanyi.com/blog/oi-icpc/notes/floating-point-sqrt>

用整数部分与小数部分分别表示平方根的精度技巧。

给你讲个鬼故事。

有一只**神犇**叫 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`）来表示浮点数，精度也会高很多。