|
|
back to boardHint? Can someone give me a hint for this task? Thanks! Re: Hint? 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 Re: Hint? Edited by author 05.08.2008 19:49 Re: Hint? overall complexity is O(N^3) |
|
|