公式解説の内容を前提とします。

凸包を求めるところまでは、\(64\operatorname{bit}\) 整数の範囲内で自然に計算できます。 よって、この問題は整数の組の列 \(d=\big((x _ i,y _ i)\big) _ {0\leq i\leq k}\ (\vert x _ i\vert,\vert y _ i\vert\leq2\times10^9)\) について、次の値を求めることに帰着されます。

\[X=\sum _ i\sqrt{{x _ i} ^ 2+{y _ i} ^ 2}\]

次の \(2\) つのパートに分けて誤差を評価します。

1. \(f(a,b)=\sqrt{a ^ 2+b ^ 2}\) の計算にかかる誤差
2. 総和にかかる誤差

計算に用いる浮動小数点数の仮数部のビット数を \(b\operatorname{bit}\) とします。 double では \(b=52\) 、long double では \(b=63\) です。 このとき、ある数を浮動小数点数にキャストするときに生じる相対誤差はたかだか \(2 ^ {-(b+1)}\) です。

1. \(f(a,b)=\sqrt{a ^ 2+b ^ 2}\) の計算にかかる誤差

\(0\leq a\leq b\) として一般性を失いません。

この計算にはいくつかの方針があります。

1. \(a ^ 2+b ^ 2\) を整数で計算し、それを浮動小数点数にキャストして平方根を取る。
2. \(a,b\) を浮動小数点数で持ち、\(a ^ 2+b ^ 2\) を計算して平方根を取る。
3. \(a,b\) を浮動小数点数で持ち、\[b\sqrt{\left(\dfrac{a}{b}\right) ^ 2+1}\] を計算する。

それぞれ評価します。

1. \(a ^ 2+b ^ 2\) は \(64\operatorname{bit}\) 整数におさまります。浮動小数点数にキャストした際に生じる相対誤差はたかだか \(2^{-(b+1)}\) です。 平方根を計算する際に生じる相対誤差もたかだか \(2^{-(b+1)}\) であるので、全体で相対誤差はたかだか \(\dfrac32\times2^{-(b+1)}\left(1+2^{-(b+3)}\right)\) になります。
2. \(a,b\) は正確に浮動小数点数にキャストできます。 \(a ^ 2,b ^ 2\) （\({}={}\)a * a, b * b）を計算する際に生じる相対誤差はたかだか \(2^{-(b+1)}\) で、和を計算する際に生じる相対誤差も \(2^{-(b+1)}\) なので、a * a + b * b の相対誤差はたかだか \(2^{-b}\) です。1. と同様にして、全体で相対誤差はたかだか \(2^{-b}\left(1+2^{-(b+3)}\right)\) です。
3. \(\dfrac ab\) を計算する際に生じる相対誤差はたかだか \(2^{-(b+1)}\) です。 \(\left(\dfrac ab\right)^2\) を計算する際に生じる相対誤差は \(3\times2^{-(b+1)}\left(1+2^{-(b+1)}+2^{-2(b+1)}/3\right)\) です。 \(a\leq b\) より、絶対誤差も同じ値で上から抑えられます。 \(1\) との和の絶対誤差はたかだか \(2^{-(b-1)}\left(1+3\times2^{-(b+3)}+2^{-2(b+2)}\right)\) で、これの平方根を \(b\) とかけた結果の相対誤差はたかだか \(2^{-(b-1)}\left(1+9\times2^{-(b+4)}+5\times2^{-(2b+5)}\right)\) です。

特に、どの方針でも相対誤差はたかだか \(5\times2^{-(b+1)}\) です。

2. 総和にかかる誤差

一般に、浮動小数点数で正確に表された数 \(a,b\in\mathbb{R} _ {\gt0}\) の和 \(a+b\) を浮動小数点数で表現するのにかかる絶対誤差はたかだか \((a+b)\times2^{-(b+1)}\) で、特に \(a+b\lt C\) のときたかだか \(C\times 2^{-(b+1)}\) です。

よって、総和を取るべき項数を \(k+1\) 項として、（愚直に先頭から和を取ったとき）総和にかかる絶対誤差はたかだか \(Xk\times 2^{-(b+1)}\) です。 完全二分木状に和を取ると、深さごとに結果の和が抑えられ、絶対誤差がたかだか \(X(\lfloor\log _ 2 k\rfloor+1)\times2^{-(b+1)}\) と評価できます（いわゆる pairwise summation です）。

よって、計算結果の真の値からの相対誤差は \((k+5)\times2^{-(b+1)}\) や \((\lfloor\log _ 2 k\rfloor+6)\times2^{-(b+1)}\) などで抑えられ、double で計算するとき前者はたかだか \(3\times10^{-11}\) 、後者はたかだか \(3\times10^{-15}\) です。

真の値からの絶対誤差もしくは相対誤差がたかだか \(10^{-6}\) であれば正答となるので、（答えを十分な精度で出力することで）以上の方針で AC が可能であることが示されました。