Here's a technique to do [C — New Year and Curling](http://codeforces.com/contest/908/problem/C) in $O(n\log n)$ time with segment tree. Brute force $n^2$ is of course fast enough, but I think speeding it up was interesting.↵
↵
Suppose we are about to place disk $i$ at $x_i$. The relevant x range we should look for disks is $[x_i-2r, x_i+2r]$ because things outside of this range are too far away to intersect with this disc. Say we find $j$ such that $j<i$, $x_j$ is in the needed range, and $y_j$ is maximized. We can find such $j$ with a basic segment tree in $\log n$ time. The intuition behind the $n\log n$ approach is that $y_i'=y_j+\sqrt{4r^2-(x_i-x_j)^2}$ is a good lower bound for $y_i$. Specifically, $y_i<y_i'+2r$ as shown by the diagram:↵
↵
↵
↵
In this worst case scenario we find that disk $j$ corresponds to the left disk. However, another disk is centered at $(x_i,y_j-\epsilon)$. So $y_i'$ in this case is $y_j$ but the true answer is $y_j+2r-\epsilon$. If we could find the second-highest circle with our segment tree, we'd get the answer right in this case. We can do this by first querying $[x_i-2r, x_i+2r]$ and getting back a result $x_{q1}$. Assume $x_{q1}<x_i$ (the other case is symmetric); we next query $(x_{q1},x_i+2r]$. Say this second query result is $x_{q2}$ with $x_{q2}>x_i$ (again other case is symmetric); we next query $(x_q,x_{q2})$ to get the third-highest circle. If we do this just a few times we're guaranteed to get the right answer.↵
↵
The reasoning behind this is that a constant number of circles fit in the "relevant area," regardless of what $n$ or $r$ are. The relevant area is a $4r$ x $2r$ rectangle horizontally centered at $x_i$ and with the top y value $y_{q1}$. It's the black box in the diagram above. If a disk's center is horizontally outside this range, the disk won't intersect the query disk. If the disk is below the relevant area, it's too low to matter ($y_i'$ is higher). And no disk can be above this area because of how $y_{q1}$ is defined. The relevant box has area $8r^2$, and any circle centered in it must occupy at least $\pi r^2/4$ area, so at most 10 circles inside of the box. So, if we do our procedure 10 times (so 10 segment tree queries), we're guaranteed to get the answer. 10 is a pretty loose bound and I got AC with 4.↵
↵
**[See AC code here](http://codeforces.com/contest/908/submission/33797584)**
↵
Suppose we are about to place disk $i$ at $x_i$. The relevant x range we should look for disks is $[x_i-2r, x_i+2r]$ because things outside of this range are too far away to intersect with this disc. Say we find $j$ such that $j<i$, $x_j$ is in the needed range, and $y_j$ is maximized. We can find such $j$ with a basic segment tree in $\log n$ time. The intuition behind the $n\log n$ approach is that $y_i'=y_j+\sqrt{4r^2-(x_i-x_j)^2}$ is a good lower bound for $y_i$. Specifically, $y_i<y_i'+2r$ as shown by the diagram:↵
↵
↵
↵
In this worst case scenario we find that disk $j$ corresponds to the left disk. However, another disk is centered at $(x_i,y_j-\epsilon)$. So $y_i'$ in this case is $y_j$ but the true answer is $y_j+2r-\epsilon$. If we could find the second-highest circle with our segment tree, we'd get the answer right in this case. We can do this by first querying $[x_i-2r, x_i+2r]$ and getting back a result $x_{q1}$. Assume $x_{q1}<x_i$ (the other case is symmetric); we next query $(x_{q1},x_i+2r]$. Say this second query result is $x_{q2}$ with $x_{q2}>x_i$ (again other case is symmetric); we next query $(x_q,x_{q2})$ to get the third-highest circle. If we do this just a few times we're guaranteed to get the right answer.↵
↵
The reasoning behind this is that a constant number of circles fit in the "relevant area," regardless of what $n$ or $r$ are. The relevant area is a $4r$ x $2r$ rectangle horizontally centered at $x_i$ and with the top y value $y_{q1}$. It's the black box in the diagram above. If a disk's center is horizontally outside this range, the disk won't intersect the query disk. If the disk is below the relevant area, it's too low to matter ($y_i'$ is higher). And no disk can be above this area because of how $y_{q1}$ is defined. The relevant box has area $8r^2$, and any circle centered in it must occupy at least $\pi r^2/4$ area, so at most 10 circles inside of the box. So, if we do our procedure 10 times (so 10 segment tree queries), we're guaranteed to get the answer. 10 is a pretty loose bound and I got AC with 4.↵
↵
**[See AC code here](http://codeforces.com/contest/908/submission/33797584)**
