Consider performing exhaustive search within a certain range.

First, we enumerate all possible \(x\), which we can prove spans from \(0\) through \(\lceil \sqrt{D}\rceil\).

Proof: if \(x\) is greater than \(\lceil \sqrt{D}\rceil\), then it is optimal to set \(y=0\), but \(|x^2+y^2-D|\) here is obviously greater than when \(x=\lceil \sqrt{D}\rceil\) and \(y=0\).

For a fixed \(x\), it is boiled down to a minimization problem of \(|y^2 + C|\), where \(C=x^2-D\).

If \(C\) is non-negative, \(y=0\) is obviously optimal. If \(C\) is negative, the optimal \(x\) is either \(y=\lfloor \sqrt{-C}\rfloor\) or \(y=\lceil\sqrt{-C}\rceil\), so we can try both.

After all, the answer for a fixed \(x\) is found in \(\mathrm{O}(1)\) time, and there are \(\mathrm{O}(\sqrt{D})\) candidates of \(x\), so this problem can be solved in a total of \(\mathrm{O}(\sqrt{D})\) time.