I have written 2 algos already:
first - O( n^3 ) - TLE #9
second - O( n^2 * log( n^2 ) ) - also TLE #9

I don't know what to do... Please help!!!

it's very strange, because I solved this problem and my AC-algo O(n^2*log(n)) has time - 0.859.

Some of O(n^2logn) programs got AC and some not.
But O(n^2) programs will be quicker of course.

I wrote O(N^2*logN), but still TLE 9 :(

I got AC with algo O ( n^2 * log( n ) )
I avoided all operations with fractional numbers.
I want to know more efficient algos. Especially solutions of  Walrus  and  currently unnamed...  Can you tell about it?

Thanks Bye.

P.S. Maybe we'll discus this problem - everyone discribes his algo with his optimizations?

P.P.S sorry for BAD English :-)

Edited by author 12.04.2006 20:27

Try to avoid all division operations.
It could speed up your program :)

you first. How do it in O(N^2 * log(N)) ?

Edited by author 03.09.2006 21:37

Hi, my algo is O(N^2lg(N)) using stl map, but it runs very slowly. I am actually doing this: for every point, I move this point at position (0,0,0) and then sort the other points by the angle they have with Ox, Oy and Oz(I think this angles are called directory cosine) (I am using NO float point arithmetic to do this)... could someone help me, where could I optimize more ???

It can be done in O(n^2) with hash table instead of sorting.

For future solvers. DO NOT USE MAPS HERE.
O(n^2 * ln n) get AC in 1.5 with vector normalisation and full floating points arithmetic.