|
|
Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | Hint? | nistaman | 1239. Ghost Busters | 30 янв 2013 00:56 | 4 | Hint? nistaman 15 окт 2006 03:38 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) | Precision | Denis Koshman | 1239. Ghost Busters | 19 ноя 2011 02:25 | 3 | EPS = 1e-14 -> WA1 EPS = 1e-10 -> WA10 EPS = 1e-8 -> WA12 EPS = 1e-6 -> WA14 EPS = 1e-4 -> AC 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 | 1239 HostBasters 3-Space Math | svr | 1239. Ghost Busters | 11 апр 2007 13:03 | 4 | 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 My correction:svr8.narod.ru Not HostBasters, but Ghost Busters |
|
|
|