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.

Edited by author 17.02.2007 22:04

there is NlogN solution

Why in this case you use use brute force and random?

because my NlogN solution gives wrong answer on 16th test
and i tryed to find such test, that BruteForce answer differs
with MyNlogNSolution answer

Try to prove your algorithm.
If proof right and authors is'n mistaken you
will pass test 16 without difficulties.