I'm interested in the technique of counting the number of positive integer pairs $x$ and $y$ satisfying $x^2+y^2 \leq n$ in $O(n^{\frac{1}{3}+\epsilon})$. The basic idea is that we can only focus on the convex hull of the integer lattice points falling in the circle $x^2+y^2 \leq n$ and the number of vertices of such convex hull is $O(n^\frac{1}{3})$. By trying to find the lattice points on the convex hull quickly (in roughly amortized constant time), we are able to yield the answer in $O(n^{\frac{1}{3}+\epsilon})$. Though there is a program implementing such an idea together with the stern-brocot tree, it is still quite hard to follow. Any detail/thought/explanation on the solution is welcome.
A related problem is here, which uses essentially the same technique to find out the convex hull of the integer lattice points under the hyperbola.
Meanwhile, a proof of the number of integer lattice points of the convex hull is $O(n^\frac{1}{3})$ is also appreciated.