Envolvente convexa e orientação

Orientação decide tudo

Envolvente é o menor convexo com todos os pontos. Guarda só vértices extremos.

$$\operatorname{cross}(p,q,r)=(q_x-p_x)(r_y-p_y)-(q_y-p_y)(r_x-p_x).$$

Positivo vira à esquerda, negativo à direita, zero é colinear. Para (0,0),(2,0),(2,2) dá 4. Com coordenadas inteiras de módulo até $10^6$, as diferenças cabem em int, mas promove para long long antes de subtrair: com coordenadas maiores, a subtração em int transborda antes de chegares à multiplicação.

Graham em três linhas

1. Tira duplicados. Pivô é o menor y, desempate pelo menor x.
2. Ordena por ângulo com cross; mesma direção do mais próximo ao mais distante.
3. Empilha e, antes de pôr q, retira enquanto cross<=0 nos dois últimos com q.

A pilha conserva curvas estritas à esquerda. Colinearidade elimina interiores. Cada ponto entra uma vez e sai no máximo uma vez: ordenação $O(n\log n)$ e varrimento $O(n)$.

No quadrado (0,0),(2,0),(2,2),(0,2) com (1,0) na fronteira e (1,1) no interior, o primeiro sai por colinearidade e o segundo por ficar interior. Ficam os quatro cantos em ordem anti-horária.

Ponto dentro do convexo

Assume um polígono convexo com h>=3 vértices extremos distintos em ordem anti-horária. Com menos de três pontos, testa igualdade ou pertença ao segmento.

1. Fora se cross(v[0],v[1],p)<0 ou cross(v[0],v[h-1],p)>0.
2. Zero pede teste ao segmento, não só à reta.
3. Pesquisa o setor com bisseção nos raios e testa a aresta exterior com cross>=0.

Custa $O(\log h)$.

Traço completo.