Goodbye 2017 C in n log n

Revision en2, by sammyMaX, 2017-12-30 05:22:53

Here's a technique to do C — New Year and Curling in time with segment tree. Brute force n2 is of course fast enough, but I think speeding it up was interesting.

Suppose we are about to place disk i at xi. The relevant x range we should look for disks is [xi - 2r, xi + 2r] because things outside of this range are too far away to intersect with this disc. Say we find j such that j < i, xj is in the needed range, and yj is maximized. The intuition behind the approach is that is a good lower bound for yi.

Tags #geometry, #data structure

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English sammyMaX 2017-12-30 05:39:33 0 (published)
en3 English sammyMaX 2017-12-30 05:38:31 1786 Tiny change: ' 4.\n\n**[Code here](' -> ' 4.\n\n**[See AC code here]('
en2 English sammyMaX 2017-12-30 05:22:53 628 Tiny change: 'i-x_j)^2}$' -> 'i-x_j)^2}$ is a good lower bound for $y_i$.'
en1 English sammyMaX 2017-12-30 05:18:38 47 Initial revision (saved to drafts)