Goodbye 2017 C in n log n

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Here's a technique to do C — New Year and Curling in $\text{[math]}$ time with segment tree. Brute force n² 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 $\text{[math]}$ time. The intuition behind the $\text{[math]}$ approach is that $\text{[math]}$ 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 - ε). So y_i' in this case is y_j but the true answer is y_j + 2r - ε. 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², and any circle centered in it must occupy at least π r² / 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

sammyMaX's blog