| ENG RUS | Timus Online Judge |
Discussion of Problem 1239. Ghost Bustersnistaman Hint? [3] // Problem 1239. Ghost Busters 15 Oct 2006 03:38 Can someone give me a hint for this task? Thanks! Denis Koshman Re: Hint? [2] // Problem 1239. Ghost Busters 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 Denis Koshman Re: Hint? // Problem 1239. Ghost Busters 5 Aug 2008 19:08 Edited by author 05.08.2008 19:49 ilya trofimov Re: Hint? // Problem 1239. Ghost Busters 30 Jan 2013 00:56 overall complexity is O(N^3) Denis Koshman Precision [2] // Problem 1239. Ghost Busters 6 Aug 2008 01:29 EPS = 1e-14 -> WA1 EPS = 1e-10 -> WA10 EPS = 1e-8 -> WA12 EPS = 1e-6 -> WA14 EPS = 1e-4 -> AC Denis Koshman Re: Precision // Problem 1239. Ghost Busters 6 Aug 2008 01:31 P.S: No trigonometry. Just a lot of additions/multiplications/divisions and 2 levels of square roots. Type: double (8-byte) Erop [USU] Re: Precision // Problem 1239. Ghost Busters 19 Nov 2011 02:25 EPS = 1e-4 -> WA5 EPS = 1e-8 -> AC svr 1239 HostBasters 3-Space Math [3] // Problem 1239. Ghost Busters 11 Apr 2007 09:47 Belive to math gives result! Got Ac (0.031) depending to previous math considerations. Difficult problem because has deal with 3-Space geometry. I remember dot product, symple topology, Kramer's formulas for linear system and win. All things will described in my site svr.narod.ru svr Re: 1239 HostBasters 3-Space Math [2] // Problem 1239. Ghost Busters 11 Apr 2007 10:25 My correction:svr8.narod.ru Alias (Alexander Prudaev) Re: 1239 HostBasters 3-Space Math [1] // Problem 1239. Ghost Busters 11 Apr 2007 12:18 Not HostBasters, but Ghost Busters svr Re: 1239 HostBasters 3-Space Math // Problem 1239. Ghost Busters 11 Apr 2007 13:03 This is my bug.
|