SoulMate Roulette

The world needs your help.

Recent scientific findings prove that everyone actually only has one soul mate, a random person somewhere in the world. Soul mate is set at birth. You know nothing about who or where they are, but - as in the romantic cliché - you'll recognize each other the moment your eyes meet.

Each person only has one randomly-assigned perfect soul mate. Fortunately, not everything is bad. The same findings show that your soul mate lives at the same time as you and are within a few years of your age (this is even stricter than the given by the standard age gap creepiness formula).

With the same-age restriction, most of us have a pool of around half a billion potential matches. Don't mind gender, sexual orientation, culture or language. Everybody has only one orientation - towards their soul mate ♥.

The odds of running into your soul mate are incredibly small.

But with the threat of dying alone looming so imminently, society has to restructure and try to enable as much eye contact as possible.

A solution could be to put together massive conveyor belts to move lines of people past each other...

Or we could use webcams...

If everyone used a system like Chatroulette for eight hours a day, seven days a week, and if it only took them a couple of seconds to decide whether someone is their soul mate, this system could - in theory - match everyone up with their soul mates in a few decades.

Many people have trouble finding any time at all for romance - few could devote two decades to it. So maybe only rich kids would be able to afford to sit around on SoulMateRoulette. Unfortunately for the proverbial 1%, most of their soul mates are to be found in the other 99%. If only 1% of people use the service, then 1% of that 1% would find their match through this system - one in ten thousand.

“Chance is a word empty of sense; nothing can exist without a cause.”

in Dictionnaire philosophique by Voltaire (1764).

So, to find an actually doable solution for this issue, all the countries decided together to bet on you - a competent computer scientist - to write a program that, in due time, is capable of pairing everyone with their correct soulmate when given the picture of everyone's eyes.

However, people are very impatient. Careers like "cashier" have already become the most sought-after ones because of the eye contact potential! So, for the next days - to speed up the process - you'll be receiving many memory cards containing eyes (every time a camera runs out of memory). Afterwards, the government's data analysts will grab all of these separate analysis of population and extract the optimal matching solution, but that's not up to you. The input/output specification is given below.

Your task

For one memory card, report the compatibility of every unordered pair of citizens. The authorities will use these scores to decide the final assignments; your output is a ranked list of pairs, not a single matching.

Input

Standard input contains exactly 532126 bytes: 1337 consecutive BMP files of 398 bytes each, without separators, a leading count or trailing bytes. Citizen identifiers are 0 to 1336 in input order.

Every BMP has the following layout:

A white pixel represents an eye-edge sample; black represents the background. Pixel-centre coordinates range from 0 to 41 on each axis. Each image must contain at least three non-collinear white points. There is one eye per citizen, and all eyes in a set are from the same side. Edges are already present in the images.

Compatibility

The shape representing each eye is the vertex set of the convex hull of its white points. Collinear points within a hull edge are not vertices. Distances refer to these vertices, not to polygon interiors or continuous edge segments.

For two vertex sets A and B, the directed and symmetric distances are defined by:

h(A,B) = max over a in A of (min over b in B of ||a-b||)
H(A,B) = max(h(A,B), h(B,A))
score(A,B) = 100 * (1 - H(A,B) / sqrt(42*42 + 42*42))

Here ||a-b|| is Euclidean distance. The denominator is fixed by the problem at sqrt(3528).

Output

For a valid input, output 893116 lines, one for each pair a < b:

a - b: score%

Pairs appear in descending order of their unrounded compatibility score. Equal scores are ordered by ascending a, then ascending b. Print the score with a decimal point and exactly two fractional digits, rounded to the nearest hundredth; for positive halfway cases, round upwards. Identifiers have no leading zeros. Each line ends with LF.

If the input length, any BMP, or any eye shape is invalid, output only:

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

These literal English lines are also required when using the Portuguese statement.

Limits

Time: 21 seconds. Memory: 550 MB.

Sample input and output

Download the binary sample and its expected output. The archive contains example_input.raw and example_output.txt; the binary input is not displayed as text.

Credits

Story and illustrations inspired by Randall Munroe’s “Soul Mates”, What If?. The invalid-input message quotes Tim Minchin’s If I Didn’t Have You.

Diogo Peralta Cordeiro · Programming Challenges (CC3036) · DCC/FCUP · 2021