SoulMate Roulette

O mundo precisa da tua ajuda.

Descobertas científicas recentes provam que cada pessoa tem uma única alma gémea: alguém escolhido ao acaso, algures no mundo, à nascença. Não sabes quem é nem onde está, mas, como no cliché romântico, reconhecer-se-ão assim que os vossos olhos se cruzarem.

Felizmente, as mesmas descobertas mostram que a tua alma gémea vive na mesma época que tu e tem uma idade próxima da tua — uma condição ainda mais restritiva do que a fórmula habitual para a diferença de idades.

Mesmo com esta restrição, a maioria de nós tem cerca de quinhentos milhões de candidatos possíveis. Esquece o género, a orientação sexual, a cultura ou a língua: cada pessoa só tem uma orientação, para a sua alma gémea. As probabilidades de a encontrar são minúsculas.

Perante a ameaça de morrer sozinho, a sociedade precisa de se reorganizar para tornar possível o maior número de encontros de olhares.

Poderíamos construir enormes tapetes rolantes para fazer passar filas de pessoas umas pelas outras…

Ou poderíamos usar câmaras de vídeo…

Se todos usassem um sistema como o Chatroulette durante oito horas por dia, sete dias por semana, e bastassem alguns segundos para reconhecer a pessoa certa, seria teoricamente possível encontrar todas as almas gémeas em algumas décadas.

Mas muitas pessoas mal conseguem arranjar tempo para o romance, quanto mais dedicar-lhe vinte anos. Talvez só os mais ricos pudessem passar o dia no SoulMateRoulette. Infelizmente para esse 1%, a maioria das suas almas gémeas encontra-se nos outros 99%. Se apenas 1% da população usar o serviço, só 1% desse grupo encontrará a sua cara-metade: uma pessoa em dez mil.

«Acaso é uma palavra vazia de sentido; nada pode existir sem uma causa.»

Voltaire, Dictionnaire philosophique (1764).

Para encontrar uma solução viável, todos os países decidiram apostar em ti, uma pessoa competente em informática, para escrever um programa que analise fotografias dos olhos da população.

As pessoas estão impacientes. Profissões como operador de caixa já se tornaram as mais procuradas pelo seu potencial de contacto visual! Nos próximos dias vais receber cartões de memória, à medida que as câmaras ficam sem espaço. Os analistas do governo irão reunir estas análises parciais para decidir as correspondências finais. Essa decisão não é tua: a especificação da tua tarefa vem a seguir.

A tua tarefa

Para cada cartão de memória, apresenta a compatibilidade de todos os pares não ordenados de cidadãos. O resultado é uma lista ordenada de pares, não uma atribuição final de almas gémeas.

Entrada

A entrada padrão contém exatamente 532126 bytes: 1337 ficheiros BMP consecutivos de 398 bytes cada, sem separadores, contagem inicial ou bytes adicionais. Os identificadores dos cidadãos vão de 0 a 1336, pela ordem de entrada.

Cada píxel branco representa um ponto do contorno do olho; o preto é o fundo. As coordenadas dos centros dos píxeis variam entre 0 e 41 em cada eixo. Cada imagem tem de conter pelo menos três pontos brancos não colineares. Existe um olho por cidadão e todos os olhos de um conjunto são do mesmo lado. As imagens já contêm os contornos.

Compatibilidade

A forma que representa cada olho é o conjunto de vértices do invólucro convexo dos seus pontos brancos. Os pontos colineares no interior de uma aresta não são vértices. As distâncias referem-se a estes vértices, não ao interior dos polígonos nem aos segmentos contínuos das arestas.

Para os conjuntos de vértices A e B, definem-se:

h(A,B) = máximo, para a em A, do mínimo de ||a-b|| para b em B
H(A,B) = max(h(A,B), h(B,A))
score(A,B) = 100 * (1 - H(A,B) / sqrt(42*42 + 42*42))

||a-b|| é a distância euclidiana. O denominador definido pelo problema é sqrt(3528).

Saída

Para uma entrada válida, escreve 893116 linhas, uma por par a < b:

a - b: score%

Os pares surgem por ordem decrescente de compatibilidade, antes de qualquer arredondamento. Em caso de igualdade, ordenam-se por a crescente e depois por b crescente. A percentagem usa ponto decimal e exatamente duas casas decimais, arredondadas à centésima mais próxima; nos empates positivos, arredonda para cima. Os identificadores não têm zeros à esquerda. Cada linha termina em LF.

Se o tamanho da entrada, algum BMP ou alguma forma forem inválidos, escreve apenas estas linhas literais em inglês:

And if it wasn't for you, baby,
I really think that I would
have somebody else.

Limites

Tempo: 21 segundos. Memória: 550 MB.

Exemplo de entrada e saída

Descarregar a entrada binária e a saída esperada. O arquivo contém example_input.raw e example_output.txt; a entrada binária não é apresentada como texto.

Créditos

História e ilustrações inspiradas em «Soul Mates», What If?, de Randall Munroe. A mensagem de entrada inválida cita If I Didn’t Have You, de Tim Minchin.

Diogo Peralta Cordeiro · Programação Competitiva (CC3036) · DCC/FCUP · 2021