Can someone give me a hint for this task?
Thanks!

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

Edited by author 05.08.2008 19:49

overall complexity is O(N^3)