My solution way getting TLE - on test 32 - while my complexity was O(n ^ 2) I think;
but by changing some parameters - coordinates for example - from int to short int, (a 4 byte variable to a 2 byte one) got AC in .3 s.
I thought may help you!
Good luck :)