é verdade, a "gravata borboleta" dá problema..
Acho que aconteceu de ela ter uma caracteristica que eu não esperava,na curva poligonal da gravata borboleta, existe uma subsequência (própria) de vértices e arestas que formam em si uma curva poligonal fechada (certo?).
E se agora eu for mais cuidadoso e verificar se a curva poligonal dada na entrada não possui essa característica? (tipo um pré-processamento). Se ela possuir a característica, eu respondo "a curva não é simples".
Pra detectar a característica eu poderia usar o que foi pedido em um exercício do par de pontos mais próximo: em tempo O(nlogn), remover pontos repetidos da coleção. Usariamos esse algoritmo (dois sorts, sendo um estável) para acusar pontos repetidos na curva poligonal dada (a menos do v_0 e v_n-1, que são os únicos que podem (e até devem) ser repetidos)
Fórum