Tiago Madeira

Há exatos 43 anos foi escrito o primeiro RFC (Request for Comments), motivo pelo qual muitos comemoramos no dia 7 de abril o nascimento da Internet. Imagino que poucas pessoas já leram ou sabem o que são RFCs fora do meio nerd: em resumo, são simples documentos de texto com não mais de 80 caracteres de largura que regulamentam os protocolos usados na Internet e são fundamentais para o desenvolvimento dos programas que você usa diariamente, inclusive o que você está usando para abrir o meu blog (seja no seu computador, no seu celular, ou no seu óculos).

Traduzi para o português (meio correndo e talvez porcamente; me corrijam se acharem alguma coisa muito errada) e recomendo a leitura do texto abaixo, escrito pelo cara que fez o primeiro RFC e publicado pelo The New York Times há três anos (para o aniversário de 40 anos da Internet). Além do valor histórico, acho que é um texto que tem muito a ver com o debate sobre as possibilidades que a internet do Wikileaks e do Mega Upload nos abre hoje e sobre os valores democráticos da rede, que têm sido duramente combatidos pelo conservadorismo do governo dos Estados Unidos e por iniciativas como a SOPA nos EUA e a Lei Azeredo no Brasil.

Como a Internet obteve suas regras

_* Stephen Crocker_

Hoje é uma data importante na história da Internet: é o aniversário de 40 anos dos chamados RFCs (Request for Comments). Fora da comunidade técnica, poucos sabem o que são RFCs, mas esses simples documentos moldaram o funcionamento interno da Internet e têm desempenhado um papel significativo no seu sucesso.

Quando os RFCs nasceram, não havia a World Wide Web. Mesmo no final de 1969, havia apenas uma rede rudimentar ligando quatro computadores em quatro centros de pesquisa: a UC Los Angeles, o Stanford Research Institute, a UC Santa Barbara e a Universy of Utah em Salt Lake City. O governo financiou a rede e os cem ou menos cientistas da computação que a utilizaram. Era uma comunidade tão pequena que todo mundo se conhecia.

Muito planejamento e muitas deliberações tinham sido feitos sobre a base da tecnologia da rede, mas ninguém tinha pensado muito no que fazer com ela. Então, em agosto de 1968, um punhado de estudantes e funcionários dos quatro locais começaram a se reunir intermitentemente pessoalmente para tentarem descobrir. (Fui sortudo o suficiente para ser um dos estudantes da UCLA incluídos nessas grandes discussões.) Só na primavera seguinte nós percebemos que deveríamos começar a escrever nossos pensamentos. Pensamos que talvez devêssemos juntar memorandos temporários e informais sobre os protocolos da rede, as regras pelas quais os computadores trocam informação. Me ofereci para organizar nossas primeiras notas.

O que deveria ser uma tarefa simples acabou se tornando um projeto desesperador. Nossa intenção era apenas encorajar outras pessoas a dialogarem, mas fiquei preocupado que soasse como se estivéssemos tomando decisões oficiais ou afirmando autoridade. Na minha cabeça, eu estava incitando a ira de algum professor de prestígio em algum estabelecimento da Costa Leste. Eu estava realmente perdendo o sono com a coisa toda e quando finalmente decidi escrever meu primeiro memorando, que lidava com a comunicação básica entre dois computadores, era madrugada. Tive que trabalhar no banheiro para não incomodar os amigos com quem eu estava hospedado, que estavam todos dormindo.

Ainda com medo de soar presunçoso, rotulei a nota “Request for Comments” (Pedido de Comentários). O RFC 1, escrito 40 anos atrás, deixou muitas perguntas sem resposta e logo se tornou obsoleto. Porém, os RFCs se enraizaram e floresceram. Eles se tornaram o método formal de publicar padrões do protocolo da Internet, e hoje são mais de 5000, todos disponíveis online.

Começamos a escrever essas notas antes que nós tivéssemos e-mail e mesmo antes que a rede estivesse realmente funcionando, então nós escrevíamos nossas visões para o futuro no papel e mandávamos pelo correio. Enviávamos uma impressão para cada grupo de pesquisa e eles tinham que tirar suas cópias.

Os primeiros RFCs variavam de grandes visões para detalhes mundanos, embora o segundo rapidamente tenha se tornado o mais comum. Menos importante do que o conteúdo desses primeiros documentos era o fato de que eles eram disponíveis de forma gratuita e qualquer um poderia escrever um. Em vez de um modelo de tomada de decisão baseado em autoridade, nós confiamos num processo que chamamos de “consenso básico e código em execução”. Todo mundo era bem-vindo a propôr ideias e, se pessoas suficientes gostassem e usassem, o projeto se tornava um padrão.

No fim, todos entendiam que havia uma utilidade prática em escolher fazer a mesma tarefa da mesma forma. Por exemplo, se quiséssemos mover um arquivo de uma máquina para a outra, se você projetasse o processo de uma forma e eu projetasse de outra, então qualquer pessoa que quisesse falar com nós dois teria que usar duas formas diferentes para fazer a mesma coisa. Então houve muita pressão natural para evitar tais inconvenientes. Provavelmente ajudou que naqueles dias nós evitávamos patentes e outras restrições; sem incentivo financeiro para controlar os protocolos, era muito mais fácil chegar a acordos.

Isso foi o melhor para a abertura dos projetos técnicos, e a cultura dos processos abertos foi essencial para permitir que a internet crescesse e evoluísse da forma tão espetacular como fez. Na verdade, nós provavelmente não teríamos a web sem eles. Quando os físicos do CERN quiseram publicar um monte de informações numa forma que as pessoas pudessem facilmente pegá-las e adicionarem às mesmas, eles simplesmente construíram e testaram suas ideias. Por causa do fundamento que colocamos no RFC, eles não tiveram que pedir permissão, ou fazerem quaisquer mudanças nas operações básicas da Internet. Outros logo copiaram-os — centenas de milhares de usuários de computador, então centenas de milhões, criando e compartilhando conteúdo e tecnologia. Isso é a Web.

Posto de outra forma, nós sempre tentamos projetar cada novo protocolo para ser útil tanto para seu próprio fim como para serem um bloco de construção disponível para outros. Nós não pensamos nos protocolos como produtos acabados, mas deliberadamente expusemos suas arquiteturas internas para fazer fácil que os outros os aproveitassem. Isso era a antítese da atitude das velhas redes de telefonia, que desencorajavam fortemente quaisquer acréscimos ou utilizações que elas não haviam sancionado.

É claro que o processo para publicar ideias e escolher padrões eventualmente se tornou mais formal. Nossas reuniões soltas e anônimas cresceram e se semi-organizaram no que chamamos de Network Working Group (Grupo de Trabalho da Rede). Nas quatro décadas desde lá, esse grupo evoluiu, se transformou algumas vezes e hoje é a Internet Engineering Task Force (Força de Tarefa da Engenharia da Internet). Ela tem alguma hierarquia e formalidade, mas não muita, e continua a ser gratuita e acessível a qualquer um.

Os RFCs cresceram também. Eles não são mais realmente pedidos de comentários, porque eles são publicados somente depois de muita examinação. Mas a cultura que foi construída no início continuou a desempenhar um papel importante em manter as coisas mais abertas do que elas poderiam ter sido. Ideias são aceitas e classificadas pelos seus méritos, com tantas ideias rejeitadas como aceitas.

A medida que reconstruirmos nossa economia, espero que tenhamos em mente o valor da transparência, especialmente em indústrias que raramente a tiveram. Seja na reforma do sistema de saúde ou na inovação da energia, as maiores recompensas virão não do que o pacote de incentivo paga diretamente, mas das perspectivas que abrimos para os outros explorarem.

Me lembrei do poder e da vitalidade dos RFCs quando eu fiz a minha primeira viagem para Bangalore, India, há 15 anos atrás. Fui convidado a dar uma palestra no Indian Institute of Science e durante a visita fui apresentado a um estudante que construiu um sistema de software bastante complexo. Impressionado, perguntei onde ele havia aprendido a fazer tudo aquilo. Ele respondeu simplesmente: “Eu baixei os RFCs e li.”

_* Stephen D. Crocker escreveu o primeiro RFC há exatos 43 anos._

Mohammad Mahdian * (tradução: Tiago Madeira)

Os levantes recentes no Oriente Médio demonstraram a eficácia da internet em ajudar ativistas políticos e sociais a organizarem protestos, disseminarem informações para o público e enviarem notícias de prisões e repressões ao restante do mundo. Ameaçados por esse paradigma, regimes totalitários tentaram controlar e monitorar o acesso de seus cidadãos à web, desenvolvendo ou adquirindo tecnologias de censura e de vigilância da internet. Ao mesmo tempo, uma variedade de ferramentas de violação desses filtros foi desenvolvida para ajudar os usuários a contornarem o filtro da internet acessando sites bloqueados através de intermediários não-bloqueados (os chamados proxies). O artigo de Dan Boneh (Recent Ideas for Circumventing Internet Filtering) dá um ótimo resumo sobre novas e velhas técnicas para construir essas ferramentas.

No coração de todos os métodos de violação existe o seguinte dilema: Para fazer a ferramenta disponível ao público, os endereços de proxy precisam ser comunicados para os usuários. Isso, no entanto, permite que as autoridades obtenham esses endereços (fingindo serem usuários legítimos) e aí bloqueiem todo o tráfego nesses endereços específicos. Ter vários proxies de curta duração alivia o problema, mas a questão permanece: Existe algum método algorítmico esperto para distribuir proxies que diminua o número de proxies necessários para fornecer acesso à internet sem filtro?

O problema de distribuição de proxy

Vamos começar definindo um modelo teórico simples para este problema. Nós gostaríamos de distribuir um conjunto de m proxies para uma população de n usuários: k deles são adversários (agentes da censura) e o restante (n-k) são usuários legítimos. Nós não sabemos as identidades dos adversários, mas podemos assumir que k « n. Na verdade, para simplicidade, pense em k como uma constante, enquanto n cresce ao infinito.

Se um proxy é dado a um adversário, ele pode comprometer o proxy, tornando-o inutilizável para os outros usuários. Uma vez que um proxy é comprometido, nós ficamos sabendo e podemos distribuir outros proxies para os usuários afetados. Nossa meta é garantir que todo usuário legítimo tenha pelo menos um proxy não-comprometido. A questão é: qual é o menor m com o qual conseguimos fornecer essa garantia?

Claramente, o problema pode ser resolvido com n proxies dando pra cada usuário um proxy diferente. Na verdade, podemos fazer muito melhor usando um algoritmo de busca binária: Comece dividindo os usuários em duas caixas e dê pra cada caixa o seu proxy. Uma vez que um proxy é comprometido, divida sua caixa correspondente pela metade e dê para cada uma das metades um proxy. Continue fazendo isso enquanto existe apenas um usuário na caixa. É fácil ver que esse método usa no máximo O(log(n)) proxies. Uma divisão cuidadosa dos usuários em caixas rende uma solução com no máximo \(k(1+log_2(n/k))\) proxies.

Podemos resolver o problema com menos de O(log(n)) proxies? Talvez surpreendentemente, nós podemos fazer um pouco melhor. Há um algoritmo randomizado de distribuição de proxies que usa no máximo O(log(n)/loglog(n)) proxies. Um argumento simples de entropia mostra que isso é assintoticamente ótimo para um k constante.

Distribuição de proxies via redes de confiança

Uma forma comum de construir uma base de usuários num país sob censura é através de relações pessoais de confiança. O sistema começa com poucos usuários confiáveis e então cada usuário confiável pode convidar novos usuários em quem ele confia para o sistema. Dessa forma, o conjunto de usuários cresce como uma rede de confiança: uma árvore enraizada na qual o conjunto de usuários confiáveis inicial é filho da raiz e arestas indicam relações de confiança.

Usar uma rede de confiança dificulta que um adversário se infiltre na base de usuários. No entanto, o problema é que uma vez que a rede é infiltrada, o adversário pode convidar novos adversários para a rede. Para levar isso em conta, nós modificamos a formulação do problema como segue: em vez de exigir que um pequeno número de usuários seja adversário, nós assumimos que um pequeno número de usuários e todos os seus descendentes na rede são adversários. Uma forma alternativa de formular esse problema é considerar redes de confiança capacitadas e assumir que o menor corte da raiz para todos os adversários é no máximo um pequeno número k.

O problema de distribuição de proxy em redes de confiança está ainda sem solução em geral. Temos resultados parciais para pequenos k e no caso capacitado. Os algoritmos são não-triviais e precisam olhar para a estrutura da rede de confiança.

Conclusão

O objetivo desse exercício era convencer o leitor de que existe um problema teórico interessante e desafiante no âmago das tecnologias de violação de censura. Modelos e algoritmos para esse problema estão muito próximos dos que são usados na prática e, logo, há potencial para pesquisa nessa área que pode ter um impacto real nas vidas de milhões de pessoas vivendo sob opressão.

* Mohammad Mahdian é um pesquisador senior do Yahoo Research Lab em Santa Clara, CA. É bacharel em Engenharia da Computação pela Universidade de Tecnologia de Sharif, mestre em Ciência da Computação pela Universidade de Toronto e PhD em Matemática pelo MIT. Seus interesses de pesquisa atuais incluem projeto de algoritmos, economia algorítmica e aplicações em publicidade online e redes sociais.

Este texto foi publicado em inglês na última edição da XRDS (revista da ACM para estudantes), cujo tema é Ciência da Computação a serviço da democracia. No site do autor, há o artigo “Fighting censorship with algorithms” completo em PDF disponível para download gratuito. Ainda não li, mas parece interessante.

Resolvi fazer Ciência da Computação há muito tempo. Faz tanto tempo que eu não lembro quando foi, mas acho que eu tinha uns oito anos. Minha única certeza é que eu não fazia ideia do que era o curso (mas isso não importa — hoje acho que escolhi estudar uma das coisas mais legais que existem).

O tempo passou e cogitei fazer outras faculdades, mas nunca seriamente. Começou o 3º ano do Ensino Médio e comparei os currículos de UFSC, UNICAMP, ICMC-USP e IME-USP pra decidir que curso escolher. Ordenei-os (por motivos teóricos) da seguinte forma:

1. IME-USP
2. ICMC-USP
3. IC-UNICAMP (engenharia)
4. UFSC

Desde lá minha meta foi entrar no lugar onde hoje, felizmente, estou. Mas não foi fácil.

Passei o último ano do Ensino Médio namorando estudando, li os resumos dos livros exigidos e quando chegou novembro… não passei na primeira fase do vestibular da Fuvest.

(Felizmente passei na UFSC e vivi um ano sensacional. Morava do lado da Universidade, fiz grandes amigos, conheci professores do mais alto nível, me classifiquei pra final mundial da Maratona de Programação e aprendi mais Matemática do que em toda a vida. Mas nem todos têm a mesma sorte.)

O vestibular da USP usa um terrível sistema baseado em carreiras.

Def. Carreiras são conjuntos disjuntos não-vazios de cursos universitários que em geral tem algo em comum (e.g., uma carreira pode ter Engenharia de Produção e Ciência da Computação porque ambos são cursos pra seres humanos — não sei se poderia haver alguma outra razão mais específica, sem ser através da Lei dos Cinco, mas creio que não).

No sistema da USP o candidato escolhe uma carreira, cursos que gostaria de fazer nessa carreira e sua ordem de preferência.

Passam pra segunda fase do vestibular três vezes o número de vagas disponíveis na carreira. Depois da segunda fase, os candidatos são ordenados de acordo com a nota da segunda fase e roda-se um algoritmo assim:

for (int pos = 0; tem_vagas_sobrando() && pos < n; pos++) {
    for (int opcao = 0; opcao < 4; opcao++) {
        if (tem_vagas_no_curso(pessoa[pos].opcao[opcao])) {
            da_vaga(pessoa[pos], pessoa[pos].opcao[opcao]);
            break;
        }
    }
}

Estava com sono e dificuldade de pensar quando postei. Outra hora tento passar pra uma língua menos nerd.

São os institutos que decidem em que carreira seus cursos vão entrar e o negócio fica uma bagunça. A maioria das carreiras têm cursos iguais com diferença apenas de período (diurno e noturno), mas há carreiras de institutos inteiros (a FEA, por exemplo, tem apenas uma carreira onde coloca Economia [diurno e noturno], Administração [diurno e noturno], Ciências contábeis [diurno e noturno] e Bacharelado em Ciências Atuariais), de cursos iguais em diferentes campi (na carreira de Direito, por exemplo, o candidato pode escolher entre o Largo São Francisco e Ribeirão Preto) e, por fim, carreiras como a minha: Engenharia na Escola Politécnica e Computação, que oferece (versão Fuvest 2010):

• Engenharia Civil e Engenharia Ambiental (poli)
• Engenharia Elétrica (ênfases: Automação e controle, energia e automação elétricas, sistemas eletrônicos, telecomunicações) (poli)
• Engenharia Mecânica e Engenharia Naval (poli)
• Engenharia Química, Engenharia Metalúrgica, Engenharia de Materiais, Engenharia de Minas e Engenharia de Petróleo (poli)
• Engenharia de Computação e Engenharia Elétrica (ênfase Computação) (poli)
• Engenharia Mecânica - Automação e Sistemas (Mecatrônica) (poli)
• Engenharia de Produção (poli)
• Bacharelado em Ciência da Computação (IME!)

Reza a lenda que essa era uma carreira que tinha todos os cursos que classificam como Exatas (uma classificação ridícula, na minha opinião) e todos eles foram saindo, até que no meu ano sobraram só as engenharias da Poli e o BCC.

(E eu prefiro acreditar nisso porque me doeria acreditar o contrário – aceitar que em certo momento da História algum idiota professor decidiu que Ciência da Computação tem mais a ver com Engenharia Ambiental do que com Matemática.)

Agora veja o problema: Em um ano aqui, aprendi que trabalhar em bancos está na moda em São Paulo. Como se formar em engenharia na Escola Politécnica é garantia desse nobre emprego, fazem um monte de cursinhos (e turmas especiais neles) voltados a destruir o cérebro das ensinar crianças (o link é bom; clique!) pra jihad passar na Fuvest. O resultado é que um catarinense que quer entrar no Bacharelado em Ciência da Computação não consegue nem passar da primeira fase do concurso. Se passa pra segunda fase, ainda assim precisa competir com estudantes que colocaram o BCC na quarta opção para não decepcionar os pais e seu ego caso não passem nas três engenharias que desejam.

E não para por aí.

O BCC abre 50 vagas por ano e neste ano matricularam-se 31 calouros. Os alunos da turma (para a qual dou monitoria da disciplina Introdução à Computação) me contaram que tem 26 pessoas indo assistir as aulas. Enquanto há jovens no Brasil inteiro querendo entrar neste curso, que considero um dos melhores (se não o melhor) do país, a sala da turma de 2010 está com metade de sua capacidade porque gente que queria fazer engenharia marcou a opção do BCC e não fez a matrícula.

A solução imediata é óbvia: tirar o Bacharelado em Ciência da Computação da carreira da Escola Politécnica.

Felizmente, não sou o único que penso isso. Então, após todo esse preâmbulo, informo em primeira mão: a Congregação do Instituto de Matemática e Estatística, em sessão ordinária realizada hoje (29/04) da qual tive o enorme prazer de participar, aprovou por unanimidade essa decisão, que já havia sido aprovada (também por unanimidade) dentro do Departamento de Computação.

Será criada nesse ano na Fuvest uma carreira chamada “Bacharelado em Ciência da Computação”, que a princípio terá 50 vagas, mas para a qual será convidado o Bacharelado em Ciência da Computação do ICMC-USP (São Carlos).

A decisão é fantástica e será fundamental pra vida de diversos futuros estudantes desta faculdade. Já estou ansioso pelo ano que vem…

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]\) é:

$$m = [ 2 w_0 w_1 , w_1 x_0 + w_0 x_1 , w_1 y_0 + w_0 q_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

$$\left| \begin{array}{ccc} w_0 & x_0 & y_0 \ w_1 & x_1 & y_1 \ w_2 & x_2 & y_2 \end{array} \right| = 0$$

, 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 ]\) é:

$$r = \langle +x_0 y_1 - y_0 x_1, -w_0 y_1 + w_1 y_0, w_0 x_1 - w_1 x_0\rangle$$

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?

O disciplina é “Princípios de Desenvolvimento de Algoritmos” e ela está sendo ministrada neste semestre pelo Prof. Dr. Carlos Eduardo Ferreira, participante do grupo de otimização combinatória, diretor nacional da Maratona de Programação e orientador da minha iniciação científica.

A turma é do Bacharelado em Ciência da Computação no IME-USP.

Acabei de receber a seguinte mensagem de um dos monitores:

Preciso dizer mais alguma coisa?