Geometria Computacional

A Geometria Computacional é uma área recente (anos 70), mas ainda assim é um tópico frequente em maratonas de programação. Contudo, os competidores devem postergar a solução de problemas desta área para o meio ou o fim do contest, pois a probabilidade de um AC é baixa por tais problemas

1. possuírem muitos corner cases, e estes casos especiais devem ser tratados com atenção e cuidado;
2. poderem receber WA devido erros de precisão inerentes às variáveis em ponto flutuante;
3. envolverem operações que são triviais quando feitas com caneta e lápis, mas se tornam razoavelmente complicadas quando precisam ser implementadas em computador;
4. apresentarem uma solução cuja codificação pode ser longa e tediosa.

Para atacar tais problemas, o competidor tem que se preparar previamente, registrando, em suas anotações, as fórmulas básicas e implementações testadas dos algoritmos clássicos da geometria.

Na implementação da solução de problemas de Geometria Computacional, valem as seguintes observações e dicas:

1. tratar todos os corner cases ou procurar implementações que os evitem;

2. evitar o uso de variáveis do tipo ponto flutuante sempre que possível;

3. se não for possível, definir um limiar (em geral, ) para o teste de igualdades:

   a == b <=> fabs(a - b) < e;
   a >= 0 <=> a > -e;
   a <= 0 <=> a < e;
   

   Uma possível implementação da igualdade em C++ é dada a seguir.

   // Comparação de igualdade entre variáveis do tipo ponto flutuante
   #define EPS 1e-9
   
   bool equals(double a, double b)
   {
       return fabs(a - b) < EPS;
   }

4. caso seja necessário usar variáveis do tipo ponto flutuante, utilizar double ao invés de float;

5. tomar cuidado com a impressão do zero: em determinados casos, pode ser impresso o sinal de negativo!

6. atentar às retas verticais, as quais podem constituir casos especiais do problema.

Há 3 abordagens possíveis para um problema de Geometria Computacional:

1. Geometria Analítica: as figuras geométricas são localizadas no espaço através das coordenadas de seus pontos/vértices. São usadas equações para representar figuras e relações, e novas relações podem ser deduzidas através da combinação e manipulação destas expressões. É a abordagem mais comum das três;
2. Geometria Plana: as figuras são descritas por suas propriedades, e a posição absoluta no espaço não é importante, apenas a distância relativa entre duas ou mais figuras. As relações são descobertas através de simetrias e semelhanças. É a abordagem menos comum, mas pode simplificar os problemas quando bem utilizada;
3. Álgebra Linear: segmentos de retas são interpretados como vetores, e transformações como rotações e translações podem simplificar problemas ao deslocá-las para uma nova origem. Muito útil para descobrir relações que seriam muito trabalhosas de se verificar utilizando apenas a Geometria Analítica.

Um bom competidor deve dominar as três abordagens, principalmente a primeira e a última. A primeira leva a fórmulas fechadas em vários casos, e é útil para montar o material de consulta. As técnicas da terceira podem ser utilizadas nas maratonas para procurar relações, simplificar problemas ou evitar corner cases, e deve ser praticada sempre que possível.

Referências

HALIM, Steve; HALIM, Felix. Competitive Programming 3, Lulu, 2013.

O'ROURKE, Joseph. Computational Geometry in C, 2nd edition, Cambridge University Press, 1998.

SKIENA, Steven S.; REVILLA, Miguel A. Programming Challenges: The Programming Contest Training Manual, Springer, 2002.