Opa, eae Vitor!
Então manin, o meu problema era que a minha solução não estava considerando todas as possíveis combinações, respeitando as condições do enunciado, entre os pontos das sublistas self.pts[p:q] e self.pts[q:r]. Ou seja, devido a uma condição de parada de um laço, o programa só testava a distância entre alguns pontos, não de todos que estavam na faixa d em relação a q e etc... Aí dava ruim no teste 16. Consertei essa condição de parada errada e ele passou no teste.
Espero que ajude!
Vlw e é nois lek!