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.