Computing integer points on the circumference of a given circle
If $a=b=0$ and $r=pq$ where $p$ and $q$ are primes congruent to 1 mod 4, then from the $O(1)$ integer points on the circle one could determine the factorization of $r$. So the problem is not going to be easier than factorization.