I originally read the problem statement as stating that the radius could only be up to 1000 in length. Hence, I was really confused when everyone was saying the problem was really easy. But that nightmare is behind me now.

I never figured out how to do it with that kind of restriction of the radius in under 1 second. What would be the optimal algorithm to use for that case?

I used the following thing :
(1) calculate median_X=sum(X[i] )/n,  do the same for Y.  (2) Teleport and find max distance from demon to Sandro.