OJ Board

You are given n vectors in 3D: a1, a2 ... an. The task is to find a unit vector d, for which the value of following expression is maximum:
|a1 x d| + |a2 x d| + ... + |an x d|.

Here,
1. all the vectors are in 3 dimension.
2. d is a unit vector.
3. a1 x d means the cross product of a1 and d.
4. |a1 x d| means the magtitute of a1 x d.

/* In an alternate way, you can think of the problem as- finding a line in 3D for which the sum of distances from n points is maximum */

How large can n be?

n canbe very large. For now, you can asume n <= 1000. Note that, for the same problem in 2D, I can think of a solution in O(n). Just take the vector summation of b1, b2 .. bn where bi is the perpendicular normal vector to ai having the same length as ai.