This solution has complexity O((N*M)^2).

Yup, I did it the same way as meooow, basically you have to rotate the coordinates by 45 degrees, then scale them by multiplying by sqrt(2), so the sqrt(2) from the numerator and denominator cancel out. As to why 45 degrees and sqrt(2), you’ll have to compare circles in both co-ordinate systems to get the answer

Could you please share its (the method you are using) resource for reference ??