Nice solution!

I came up with the exact same code character for character wtf

I think this is the fastes solution

Thanks! This is indeed a lot shorter and easier :)

Correct. Or you could use operator.attrgetter and write
vertices = sorted(vertices, key=operator.attrgetter('dist')).

def getDist(item):
    return item.dist
# ... #
vertices = sorted(vertices, key=getDist)

is typically the kind of places where lambda are elegant and useful: vertices = sorted(vertices, key=lambda item: item.dist)
(I don't mean to sound pretentious there, it's just that getDist seems funny at first sight so I thought you might not know lambdas)

Thanks for being the first person to complete this kata! The lack of previous takers is no doubt due to the difficulty level and the absence of translations to any languages other than C++. I'd given it a suggested 2kyu rating, but had been wondering if it should really be 1kyu; your opinion on that is duly noted.

This was definitely the most challenging Kata I have solved so far, but also among the most enjoyable ones.
I requires a lot of logical thinking, spatial reasoning and problem solving capacity, as well as sufficient programming skills to implement the problem solving procedure.
It took me a few days to come up with a good strategy, and a few more to implement it.
At some point, I was able to find correct solutions for all cases, but kept getting a timeout due to poor performance. It was only after I came up with better lower bounds for the remaining distance that I managed to solve all test cases in time.

It sounds like my assumptions about accuracy were too optimistic. From the numbers you quoted, you have a relative error of 7e-8 on the random test, and 3e-8 on the hexagonal grid one. (For the latter, the exact area of each hexagonal cell is the square root of 12.)

I've just now tweaked the acceptance criteria so that the relative error tolerance for finite values is now 1e-6 (i.e. errors up to 0.0001 per cent are accepted) and for the infinite areas, finite values are accepted if they are at least 1e+9. Hopefully this will allow you to do a final submission; I'll then be interested in looking at your code to see whether you're doing something I didn't anticipate.

Thanks for doing my kata.

I'm using C++, and the test is failing when a finite value is expected. For the Randomly_Placed_Seeds test, I'm getting the following error message : Wrong value for cell 2 (19.3523896053, expected 19.3523909783). The Hexagonal_Grid test is failing as well, giving a similar message : Wrong value for cell 6 (3.4641015, expected 3.46410161514)
It seems to me that I'm following a correct reasoning, and that these errors are caused by rounding differences. I'm not sure if this is something I can solve by using a better or more efficient implementation, but I'd be glad to hear if you have any ideas. If not, you might consider setting your acceptance criteria to some percentage of the expected result, instead of an arbitrary value.
Even though I'm still having some issues, I would like to thank you for writing this Kata. I spent some time thinking about the most efficient way to solve this problem, and I enjoyed the challenge.

Sorry about that; I thought I had been fairly generous in allowing for round-off error. You can see the acceptance criteria in the answer_matches() function in the Example Test Cases: where an expected area is finite, you have to match it to within a relative tolerance of 1e-9, and where the expected area is infinity (reported as -1), you have to return either -1 or a finite value >= 1e+13. Any correct algorithm using double-precision arithmetic should easily achieve this level of accuracy on the tests provided (which are deliberately constructed to avoid numerically ill-conditioned cases where accuracy would be degraded). Or so I thought when I wrote this kata.

Do you know which test your code is failing? Does it involve a finite or an infinite expected value? Also, which programming language are you using?

I liked this Kata a lot, but I did not manage to submit a working solution because of rounding differences. I would suggest to accept solutions which are close enough to your original solution, because different approaches could lead to (slightly) different solutions. Completing this Kata will be more fun without having to struggle with rounding.