(Note: the editorials are written in a hurry and without having solved the problems, so there may be mistakes. Feel free to correct them / inform me.)
PROBLEM LINK:
Author: Kevin Atienza
Tester: Sergey Kulik
Editorialist: Xellos
DIFFICULTY:
HARD
PREREQUISITES:
binary search, sqrt-decomposition
PROBLEM:
There are N points added to a plane one by one. After each point is added, count the number of triangles containing the origin (0,0).
QUICK EXPLANATION:
Solve the problem for N fixed points first, in O(N\log{N}). Count triangles which don’t contain the origin. Use sqrt-decomposition with precomputation after adding each \sqrt{N} points, deal with a lot of cases.
EXPLANATION:
SOLVING THE UNDERLYING PROBLEM
First of all, we need to solve the original problem, which is quite well-known. Instead of counting triangles containing the origin, it’s better to count triangles not containing it, since there are N(N-1)(N-2)/6 triangles to be formed from N points. All vertices of such a triangle must lie on one side of a line containing the origin (or on that line), so when we replace each point by the angle it can be seen at from the origin (the function atan2(y,x) returns exactly this angle), then the angles corresponding to vertices of a “bad” triangle will lie in an interval of length \pi; for a “good” triangle, no such interval may be found.
One approach that we’ll build on is this: sort the vertices and using sweepline by angle / 2 pointers, compute for each angle the number of points p in the range [its angle, its angle + \pi] (if several points have the same angles, we can tiebreak arbitrarily), then subtract p(p-1)/2.
Note that we have to subtract the degenerate triangles whose vertices are all collinear with the origin and two of them on opposite sides of the origin, since they will be counted twice. However, they’re easy to count - we need to reduce each point to (x,y) with coprime x,y and store those pairs in a map<>, which gives us the points on both sides of the line connecting the newly added point to the origin.
SQRT DECOMPOSITION
Let’s choose a number K close to \sqrt{N} and after processing every K points, sort the currently processed points (mergesort in O(N)) and precompute something; we’ll see what it is.
When adding a new point, the total number of triangles of any type increases by the number of those containing that point. There are N(N-1)/2 triangles added in total (for the current N); let’s convert the added point to its atan2() angle \alpha_i and binary-search its position p_i in the sorted list of the points P_B added before the last precomputation (the smallest such position in case of ties). Then, we need to count the following pairs of angles:
-
angles in the interval [\alpha_i,\alpha_i+\pi] by bruteforcing the O(K) points P_A added since the last precomputation and binsearching the last such angle among points P_B; don’t forget that angles are cyclic - \alpha \equiv \alpha+2\pi
-
for each angle \beta among P_B in the range [\alpha_i-\pi,\alpha_i), the number n_2 of angles after it in the list (watch out for equal angles) and in the range [\beta,\beta+\pi]; we need \sum n_2
-
using the algorithm for a fixed number of points, the number of triangles not containing the origin and consisting of the added point + points in P_A only, where the first point of the interval of length \pi is in P_A; note that it’s O(K) when we don’t count sorting
-
for all points in P_A with angle \beta after the added point (meaning 0 \le \beta-\alpha_i+2k\pi \le \pi for a suitable k), count the points in P_B in the range [\beta-\pi,\alpha_i) - the positions of the first and last point in this range have been binsearched before, so we can compute it in O(1)
-
for all points in P_A before the added point, count the points in P_B in the range [\alpha_i-\pi,\beta], same as above
Case 1+2 count triangles consisting of the added point and two points in P_B, cases 1+4+5 counts them for one point in P_A and another in P_B, cases 1+3 for two points in P_A. For each type, we’ve considered all three positions of the added point among the 3 angles in an interval of length \pi.
After subtracting the points forming degenerate triangles (if you read carefully, you’ll notice how they’re counted twice here), we have the updated answer in O(\log{N}+K)=O(\sqrt{N}) per query with O(N/K) recomputations, which we’ll need to do in linear time.
What was there to precompute, really? The number of angles from P_B in an interval can be found in O(1) time using only their positions (we’ll store them in an array), but in case 2, we have to find a range sum of numbers n_{2i}. Fortunately, n_{2i} can be found in O(N) total time using 2 pointers during each recomputations and since they’re fixed until the next recomputation, we only need their prefix sums to make counting range sums possible in O(1).
This way, we get an O(N^2/K+NK+N\log{N})=O(N\sqrt{N}) algorithm with O(N) memory.
AUTHOR’S AND TESTER’S SOLUTIONS:
The author’s solution can be found here.
The tester’s solution can be found here.