Conheci as coordenadas homogêneas por acaso. Era 2004, ganhei a modalidade iniciação da Olimpíada Brasileira de Informática e passei o inverno estudando C, acho que por dois motivos: interesse pelos problemas da modalidade programação e desejo de aproveitar bem o curso que os medalhistas fazem na UNICAMP; ou talvez fosse apenas falta do que fazer ou curiosidade mesmo. Não importa.

Confundo os cursos de 2004, 2005 e 2006, mas lembro que no primeiro aprendi com um monitor sobre recursão, representação de grafos e busca em profundidade. Lembro também que foi em 2004 que conheci o CLRS (livro que comprei alguns meses depois e tenho na cabeceira até hoje). Esse post, porém, é sobre um acontecimento mais aleatório relacionado a esse curso e, ouso afirmar, digno de figurar n’O Andar do Bêbado do Mlodinow.

O pessoal da modalidade programação ia tirar cópias de um livro do Stolfi e do Rezende, chamado “Fundamentos de Geometria Computacional” (dá pra baixar aqui). Nem sabia do que estavam tirando xerox, mas vi que era barato e que todos os mais velhos estavam querendo, então também pedi.

Folheei o livro, não entendi nada, deixei num canto e voltei a abrir alguns anos depois, não lembro exatamente quando. E foi aí que fez-se a luz. A primeira parte é sobre coordenadas homogêneas.

Coordenadas homogêneas? A ideia parece simples (até demais) pra ser poderosa. Basicamente você representa uma coordenada em $(X, Y) \in \mathbb{R}^2$ com uma tripla ordenada $[w, x, y]$ tal que $x = \frac{X}{w}$ e $y = \frac{Y}{w}$. A reta tem a mesma representação.

struct ponto {
	int w, x, y;
};

typedef ponto reta;

E o que isso tem demais? Você deixa de precisar de pontos flutuantes pra maioria das operações geométricas; ganha pontos no infinito (eles são a interseção entre retas paralelas!) que permitem fazer fórmulas sem preocupação com casos especiais, usar a mesma fórmula pra determinar uma reta gerada por dois pontos ou por um ponto e um vetor etc.; tem representações iguais (e dualidade) entre pontos e retas (e.g. interseção entre retas p e q = reta determinada por pontos p e q); e mais um monte de outras coisas.

Uau! Como eu não ouvi falar disso antes? Eu não sei a razão, mas, embora tenham várias vantagens, as coordenadas homogêneas não são muito populares na universidade, nem entre os maratonistas. No entanto, são usadas em projetos grandes que usam muita geometria (e.g. OpenGL).

Quero código! Vou mostrar como resolvi o problema Symmetry (2002 TopCoder Inv Round 4 – Division I, Level Three).

O enunciado é simples: Dados n ($2 \leq n \leq 200$) pontos inteiros (com coordenadas de -10000 a 10000) determinar quantas linhas de simetria existem entre eles.

Dá pra fazer em $O(n^3)$ com a seguinte ideia:

1. Crie uma árvore binária balanceada indexada por retas. (em C++, map <reta,int>)
2. Para cada par de pontos, determine a reta de simetria entre eles e adicione 2 a essa reta na árvore binária. ($O(n^2 log n)$)
3. Para cada reta na árvore binária, adicione 1 para cada ponto que pertence a essa reta. ($O(n^3)$)
4. É fácil ver que a reta é uma reta de simetria do conjunto de pontos se e somente se seu valor na árvore binária for $n$.

O problema geométrico está no segundo passo: determinar a reta de simetria entre dois pontos. Sejam esses pontos p e q. É preciso:

1. Determinar o ponto médio entre p e q.
2. Determinar a reta que passa por p e q (o enunciado garante que p != q).
3. Determinar uma reta (ou um vetor) perpendicular à reta do passo acima.
4. Determinar a reta que passa pelo ponto médio e tem a direção do vetor perpendicular do passo 3.

Determinar o ponto médio sem usar ponto flutuante seria trivial de qualquer forma (basta multiplicar todas as coordenadas por dois), mas com coordenadas homogêneas isso é desnecessário. É fácil ver que o ponto médio $m$ entre $p = [w_0, x_0, y_0]$ e $q = [w_1, x_1, y_1]$ é:

ponto ponto_medio(ponto p, ponto q) {
	return (ponto) { 2*p.w*q.w, q.w*p.x+q.x*p.w, q.w*p.y+q.y*p.w };
}

Três pontos $[w_0, x_0, y_0]$, $[w_1, x_1, y_1]$, $[w_2, x_2, y_2]$ são colineares se

, o que nos permite concluir que a reta $r = \langle W, X, Y \rangle$ que passa por $p = [ w_0, x_0, y_0 ]$ e $q = [ w_1, x_1, y_1 ]$ é:

Logo:

ponto reta_determinada_por(ponto p, ponto q) {
	return (reta) { +p.x*q.y-q.x*p.y, -p.w*q.y+q.w*p.y, +p.w*q.x-q.w*p.x };
}

(um ponto $[w, x, y]$ pertence a $r$ se $Ww + Xx + Yy = 0$)

int ponto_na_reta(ponto p, reta r) {
	return p.w*r.w + p.x*r.x + p.y*r.y == 0;
}

Agora a parte mais legal: a fórmula para determinar uma reta que passa por dois pontos funciona com pontos no infinito (pensemos em pontos no infinito como vetores, porque eles tem direção mas tem $w = 0$): o resultado é a reta determinada por um ponto e uma direção. O vetor perpendicular à reta $\langle W, X, Y \rangle$ é $[ 0, X, Y ]$.

ponto ponto_infinito_na_reta_perpendicular(reta r) {
	return (reta) { 0, r.x, r.y };
}

E isso é tudo. Agora basta criar uma representação única da reta pra guardar na árvore binária.

reta reformata_reta(reta r) {
	if (r.w < 0) {
		r.w = -r.w;
		r.x = -r.x;
		r.y = -r.y;
	} else if (r.w == 0) {
		if (r.x < 0) {
			r.x = -r.x;
			r.y = -r.y;
		} else if (r.x == 0 && r.y < 0) {
			r.y = -r.y;
		}
	}
	int d = gcd(r.w, gcd(abs(r.x), abs(r.y)));
	return (reta) { r.w/d, r.x/d, r.y/d };
}

Usando essas funções, primeiro e segundo passos da solução são:

map <reta,int> M;
for (int i = 0; i < n; i++) {
	for (int j = i+1; j < n; j++) {
		reta s = reformata_reta(reta_determinada_por(P[i], P[j]));
		ponto pm = ponto_medio(P[i], P[j]);
		ponto dir = ponto_infinito_na_reta_perpendicular(s);
		reta r = reformata_reta(reta_determinada_por(pm, dir));
		if (M.find(s) == M.end())
			M[s] = 0;
		if (M.find(r) == M.end())
			M[r] = 0;
		M[r]+= 2;
	}
}

Terceiro e o quarto são:

int output = 0;
for (map <reta,int>::iterator i = M.begin(); i != M.end(); i++) {
	for (int j = 0; j < n; j++)
		if (ponto_na_reta(P[j], i->first))
			i->second++;
	if (i->second == n)
		output++;
}

O código completo ficou com umas 90 linhas com comentários e linhas em branco e foi aceito na primeira submissão (ok, na verdade na segunda, mas não foi devido à geometria muito menos à precisão): symmetry.cpp (infelizmente, esse arquivo foi perdido com o tempo). Não é lindo?

Meu primo tuitou há alguns minutos que “o maior erro na vida é ter medo de errar” e a frase me deixou pensativo.

Suponha que você leia essa frase e resolva “Então, para não errar, não vou ter medo de errar”. Nesse caso você está tendo medo de um erro (o erro seria o medo de errar); absurdo!

Suponha, por outro lado, que você leia essa frase e resolva “Então vou continuar com medo de errar.” Neste caso, você está cometendo o maior erro (sem medo dele), então você perdeu o medo de errar. Absurdo novamente!

Portanto, conclui-se que o maior erro na vida não deve ser o medo de errar. qed.

PS: Perdoem-me por possíveis falhas, tive que escrever correndo para não me atrasar para o tango.

Aprendo muito na Universidade. Não tanto nas aulas do currículo obrigatório, mas sem dúvidas naquelas que frequento porque realmente quero aprender, principalmente quando essas me desafiam. A falta de desafio nos torna medíocres e foi a falta de desafio que me tirou a vontade de ir para as aulas no semestre passado.

Mais do que na sala de aula, porém, aprendo nas bibliotecas, corredores e gramados. Os espaços de vivência e debates são os locais mais importantes da universidade (e usuários do DaD — diploma a distância — infelizmente talvez nunca experimentem isso). Nestes espaços aprendemos e reproduzimos discursos e ideias que nos fazem pensar e criticar a realidade.

Estes espaços não tem nada de especial e não são exclusivos das universidades, mas acredito que nas universidades é mais fácil criar essas rodas porque há muitas pessoas com interesses em comum. Além disso, eles não se limitam a debates políticos e filosóficos; deles pode surgir um problema puramente matemático.

Sem mais enrolação, vou narrar o fato: Acabou ontem a primeira semana de aulas da USP. Houve recepção aos calouros em todos os cantos do campus e eu passei pelo menos 14 horas todos os dias lá caminhando principalmente entre IME, FAU e FFLCH.

Definitivamente foi uma das semanas mais interessantes que já vivi nesta universidade até o presente momento. Li ótimos livros, participei de ótimas conversas e aulas-debate e conheci várias pessoas muito interessantes. Não vou entrar em detalhes sobre tudo isso, porém, visto que isto foge do assunto que planejei pra esse texto. Pra ser sincero, agora é que percebi: toda essa introdução foi exagerada e criou falsas expectativas para os leitores. Desculpem pelo meu pensamento caótico. Com efeito, sem mais enrolação (agora eu prometo), o ponto que quero chegar é o seguinte:

Sejam a, b e c números naturais. Sejam A e B subconjuntos dos naturais. Seja f : A → B uma função natural bijetora definida por f(x) = a * ⌊x / c⌋ + ⌊(x mod c) / b⌋. Qual pode ser o conjunto A para termos B = ℕ? Qual a função inversa f⁻¹?

Não é um bom problema? Tente resolver antes de continuar a leitura.

Certo. Para manter o texto divertido (e possivelmente confuso, confesso) prosseguirei de trás pra frente.

Tuitei esse problema às 15h de quinta-feira. Antes eu havia passado algumas horas caído por causa do cansaço. Antes eu tuitei que nunca tinha pensado em inversas de funções com módulo. Isso porque eu determinei a inversa dessa estranha função que atribui uma quantidade inteira de dinheiro (em reais) a uma quantidade de cervejas. Cheguei a essa estranha função porque algumas horas antes estava vendendo fichas de cervejas na festa da Calourada Unificada do DCE da USP. Uma cerveja custava R$ 2,00 e três cervejas custavam R$ 5,00.

Simplificando o caminho, agora de frente pra trás: Trabalhar de caixa correndo pra contar dinheiro (havia muita fila) inseriu na minha mente uma estranha função que me permitiu, mesmo com extremo cansaço, criar um problema muito divertido de matemática. (Eu passei o ano passado inteiro no IME e não inventei nenhum problema que eu tenha gostado.)

Agora vem a melhor parte: o problema em linguagem matemática parece assustador para a maioria, mas sua solução é absolutamente trivial se você sabe de onde ele veio e ficar restrito ao caso em que b ≤ c. De fato, concentre-se na venda de cervejas. A pergunta “Qual pode ser o conjunto A para termos B = ℕ?” é equivalente a “Qual os valores que não necessitam troco?” e a pergunta “Qual a função inversa?” é equivalente a “Qual a função que atribui número de cervejas ao seu preço?”

Bem… Não vou me alongar porque escrever recordou-me que preciso resolver o problema pro caso geral. Aproveitem o ano & bons estudos!

Curiosamente as melhores aulas (em conteúdo e rigor matemático) que estou tendo no IME–USP neste semestre são as de Introdução à Probabilidade e Estatística I (MAE 121). Digo “curiosamente” porque

0. Nunca gostei de estatística (e acreditava que este seria o foco da disciplina);

1. Álgebra e Cálculo tem um conteúdo que acredito ser bem mais matemático;

2. Sinceramente, não esperava nada desta disciplina.

Surpreendi-me porque, de fato, desde que entramos na matéria de Probabilidade tudo até agora foi definido ou provado formalmente. Por exemplo, espaço de probabilidade é a tripla $(\Omega, F, P)$, onde $\Omega$ é o espaço amostral, $F$ é uma $\sigma$-álgebra que representa o conjunto dos eventos e $P: F \rightarrow [0, 1]$ é a função probabilidade. Com três axiomas em cima dessa definição provamos uma porção de coisas.

Muito interessante. A probabilidade é uma área que eu desconhecia completamente (e discriminava em pensamento por andar sempre junto com Estatística), mas que é muito mais legal (em nível matemático) do que eu pensava.

— A notação que os físicos e matemáticos usam para a derivada é muito ruim, não faz sentido nenhum.

— É verdade, não dá nem pra usar regra da cadeia!