给你讲个鬼故事。
有一只神犇叫 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)来表示浮点数,精度也会高很多。