Project everything onto sphere R=1, now you have 2D problem because Z can be evaluated from X and Y. Projections' countours will be circles. Then find limiting Y - i.e. Y values for which some particular projection has only one point on that R=1 sphere. Then find all Y values for which two projections start/stop intersecting. For every pair of projections there will be at most 2 such Y values, so we will have at most O(N^2) control Y points.

Now, for each particular Y value each projection will constitute some [X1;X2] interval and it becomes a classic point-in-max-number-of-segments problem (O(N*log(N)). So, the overall complexity is O(N^3*log(N)). And a lot of math about square equations.

Edited by author 05.08.2008 19:02

Edited by author 05.08.2008 19:57

Edited by author 05.08.2008 20:00

P.S: No trigonometry. Just a lot of additions/multiplications/divisions and 2 levels of square roots. Type: double (8-byte)

EPS = 1e-4  -> WA5
EPS = 1e-8  -> AC

My correction:svr8.narod.ru