18536. Capital

Olá meus amigos nerds. Hoje vamos brincar de arquitetos e ajudar o senhor Bloggs a planejar uma cidade. Já que é isso que o problema 18536. Capital nos pede para fazer. Mais especificamente, nossa tarefa é determinar, se dados quatro valores de área (a1, a2, a3 e a4) determinar se é possível formar um retângulo que tenha area igual a soma das quatro áreas.

Solução

Problemas de geometria costumam ser bastante complexos, mas esse não é muito difícil. Para começar sabemos de duas coisas: o valor de cada uma das quatro áreas e que elas são necessariamente retangulares. Entretanto não conhecemos os lados de cada retângulo (é isso que queremos determinar).

Note que juntar, quatro áreas (retangulares) e formar um retângulo é equivalente a dado um retângulo dividí-lo em quatro outros retângulos. Vamos, então resolver esse problema. Observe a figura abaixo:

Onde temos um retângulo de lados a e b. Observe que:

a = x1 + x2
b = y1 + y2

Sejam A1, A2, A3 e A4 as quatro áreas dadas. Da figura, podemos escrever as áreas como:

x1*y1 = A1
x2*y1 = A2
x1*y2 = A3
x2*y2 = A4

Note que temos quatro variáveis e quatro equações, mas infelizmente esse não é um sistema linear. Mesmo assim podemos isolar y1 nas duas primeiras equações (supondo x1 e x2 diferentes de 0):

y1 = A1/x1
y1 = A2/x2

O que implica:

A1/x1 = A2/x2 => A1*x2 = A2*x1 => A1*x2 - A2*x1 = 0

Fazendo o mesmo para y2:

y2 = A3/x1
y2 = A4/x2

O que implica:
A3/x1 = A4/x2 => A3*x2 = A4*x1 => A3*x2 - A4*x1 = 0

O que resulta no seguinte sistema homogêneo:
A1*x2 - A2*x1 = 0
A3*x2 - A4*x1 = 0

Se o sistema possuir solução única ela será trivial (x1=x2=0). Essa solução não nos serve! Já que supusemos que x1, x2, x3 e x4 eram diferentes de 0 no inicio de nossa dedução. Ou melhor, essa solução indica que não é possível construir o retângulo com as quatro áreas dadas.

Nos resta ainda a possibilidade de esse sistema ter infinitas soluções (lembre-se, um sistema homogêneo nunca é impossível). Nesse caso podemos escolher algum x1, x2, diferentes de 0 (e maiores que 0, já que se tratam de lados de um retângulo). Para isso, o determinante da equação deve ser nulo, ou seja:

A1*A4 == A2*A3

Eu queria dizer que já está resolvido, mas falta ainda uma parte importante. Em nossa discussão supusemos que conhecíamos A1, A2, A3 e A4, mas na realidade não conhecemos a ordem em que as áreas devem ser testadas na equação acima, sendo assim temos que testar todas as permutações para ter certeza que alguma satisfaz a equação.

Implementação

Quem vê esse código até pensa que o problema é muito fácil! Ledo engano...