Try some kind of "divide and conquer" algorithm. My algorithm is based on the algorithm of finding the closest pair of points, used the same pruning. Believe me, what you think is impossible this time it's possible.
i have write brute-force procedure solve() and test my program on random tests. my program always gives correct answer. I have not so twisted imagination, which have autors this tests, so i can't think up such test.
My congratulations to autors: your imagination is more twisted than rand() :)
Your should be greatful to authors who keep in secret speeding up methods and give you(and us) chance to create them. Now I can't see how avoid O(n^3) For example may be 16000 smal identical triangles and so on. I think 15-test is last with small N. So not-top-coders may move to solution by exchanging with ideas on forum.