Autor: Pedro Guerreiro (Universidade do Algarve)
Tipo de problema: Geometria
Este era um problema de carácter geométrico, sendo o mais exigente no que concerne à disciplina na programação, obrigando a uma maior organização e modularização do código. A solução para o problema é basicamente dada no enunciado e podia dividir-se em vários passos, sendo que nenhum deles é por si só demasiado complicado, mas que como um todo obrigavam a uma implementação cuidada.
A solução podia por exemplo dividir-se nos seguintes passos:
- identificação do contorno uma melancia: uma vez apanhado um M, seguir o contorno da melancia pelas células adjacentes até voltar à célula inicial. Guardar as posições das células encontradas.
- descoberta dos "cantos": na lista das células de uma única melancia, procurar os pontos cujas duas células vizinhas têm X e Y diferentes.
- verificação das tangentes: se tivermos feito o primeiro passo seguindo uma ordem definida na procura das células adjacentes, podemos garantir que a lista vem sempre no sentido dos ponteiros do relógio (ou sempre no sentido contrário). Assim, para verificar se as tangentes se comportam como esperadoa num melancia smooth, basta ver se o declive (calculado por exemplo usando a equação y=mx+b) muda de sinal apenas duas vezes.
- cálculo o centro da melancia: percorrer a lista e calcular as médias horizontais e verticais.
Ligações interessantes:
