Google Code Jam 2008 - Triangle Areas

Triangle Areas foi o segundo problema da 2a rodada on-line do Code Jam 2008. Fiquei a maior parte das duas horas da competição tentando resolvê-lo sem sucesso. Curioso, baixei as soluções dos dois primeiros colocados e me assustei com a simplicidade delas. Duas perguntas me surgiram: como eles chegaram nesta solução e como garantir que elas estão corretas. Após quase quatro dias de ruminações, a luz surgiu hoje enquanto vazia a barba.

O Problema

Raspando o problema à sua essência, são dados três números inteiros N, M e A, maiores que zero. O problema consiste em achar um triângulo (xa,ya), (xb,yb), (xc,yb) cuja área seja A/2 com x e y inteiros e 0 ≤ x ≤ N e 0 ≤ y ≤ M (ou indicar que o problema é impossível).
A Solução

A fórmula para a área de um triângulo a partir das coordenadas dos pontos que o compõe é:

|xa*yc - xa*yb + xb*ya - xb*yc + xc*yb - xc*ya|/2

É claro que os casos de teste eram grande o suficiente para tornar inviável o teste de todas as combinações por força bruta. É preciso, portanto, simplificar.

Se assumirmos que o ponto a é a origem (0,0) a fórmula se simplifica para:

|xc*yb - xb*yc|/2

Ainda assim são valores demais para a força bruta. Vamos tentar simplificar um pouco mais e assumir que xb e yc são zero, fazendo um triângulo retângulo encostado nas bordas:
Neste caso ficamos com xc*yb = A. Ou seja, precisamos quebrar A em dois fatores. Dá para perceber que um A primo e maior que N e M estraga a brincadeira (por exemplo, se N=2 e M=6 não conseguimos achar um triângulo com A=7). Simplificamos demais.

Vamos tentar fazer xb =1. Ficamos com |xc*yb - yc| = A. Será que isto resolve?

Em primeiro lugar, é óbvio que se A for maior que N*M o problema é impossível (se você não perceber isto pelas fórmulas, considere que temos um retângulo de área N*M e que o maior triângulo que conseguimos colocar nele terá área N*M/2).

A questão é: para qualquer valor de A maior que zero e menor ou igual a N*M conseguimos achar xc, yb e yc que atendam à nossa fórmula? A resposta é sim. O segredo é reparar que a fórmula se assemelha muito a uma divisão de inteiros (exceto pelo '-' ou invés de '+'): podemos considerar que xc é o quociente da divisão de A por yb e yc é uma espécie de resto.

A coisa fica mais clara se forçarmos yb = M. Ficamos com |xc*M - yc| = A. Variando xc de 1 a N e yc de 0 a M-1 conseguimos todos os valores de 1 a N*M.

O Código

Resolvido o problema, o código é incrivelmente trivial:

#include 

void main (void)
{
 int iCase, nCases;
 int N, M, A, xc;

 scanf ("%d", &nCases);
 for (iCase = 1; iCase <= nCases; iCase++)
 {
   scanf ("%d %d %d", &N, &M, &A);
   if (A > N*M)
     printf ("Case #%d: IMPOSSIBLE\n", iCase);
   else if ((A % M) == 0)
     printf ("Case #%d: 0 0 1 %d %d 0\n", iCase, M, A/M);
   else
   {
     xc = (A/M)+1;
     printf ("Case #%d: 0 0 1 %d %d %d\n", iCase, M, xc, xc*M - A);
   }
 }
}

Pena que não tive a capacidade e frieza de achar esta solução durante a competição...