Analysis for problem "D. Knights".
Denote the number of fences surrounding the control point number i through cnti. Also denote cntij - the number of fences surrounding point i and point j. Then the answer to the query (i, j) is cnti + cntj - cntij. Clearly, that we can calculate all the values cnti with time O(n * m). The problem is the fast computation of the values cntij. And then suggests two solutions: a simple and not very much. Simple is as follows: create for every point i a bitset, j-th is equal to 1 if the j-th fence surrounds the point number i. Then, obviously cntij = count(zi & zj), where count(a) - the number of ones in bitset a. Now another solution. Add another fence with a center at (0, 0) and infinite radius. We construct a graph whose vertices are the fences as follows: we draw an arc from i to j, if the i-th fence is a fence with the minimum radius surrounding the fence number j. Obviously we get a directed tree rooted at the fence of infinite radius. Also, for each control point will find idxi - number of the fence with minimum radius surrounding the i-th control point. Then cntij = distij + distji, where distij - distance from vertex i to the lowest common ancestor of verticex i ans j. With the implementation problems should not arise, because in the first solution could write bitset himself or use the standard bitset from STL (for those who write in C++), while in the second solution we could preprocess all the lca with time O(n2).