ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1239. Ghost Busters

Hint?
Posted by nistaman 15 Oct 2006 03:38
Can someone give me a hint for this task?
Thanks!
Re: Hint?
Posted by Denis Koshman 5 Aug 2008 19:02
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?
Posted by Denis Koshman 5 Aug 2008 19:08


Edited by author 05.08.2008 19:49
Re: Hint?
Posted by ilya trofimov 30 Jan 2013 00:56
overall complexity is O(N^3)