## Analysis for problem "D. Knights".

Denote the number of fences surrounding the control point number i through cnt

_{i}. Also denote cnt_{ij}- the number of fences surrounding point i and point j. Then the answer to the query (i, j) is cnt_{i}+ cnt_{j}- cnt_{ij}. Clearly, that we can calculate all the values cnt_{i}with time O(n * m). The problem is the fast computation of the values cnt_{ij}. 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 cnt_{ij}= count(z_{i}& z_{j}), 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 idx_{i}- number of the fence with minimum radius surrounding the i-th control point. Then cnt_{ij}= dist_{ij}+ dist_{ji}, where dist_{ij}- 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(n^{2}).
pre-process the relation between central points and circles(inside/outside a circle) O(N

^{2}).then answer the query in O(M), given 2 points, check which circles contain exactly 1 point outside the circle and 1 point inside the circle.

Total Complexity: O(N

^{2}+ QM) which is still ok for 2 secand total complexity O(NM+QM)

For each query (i, j), count the number of circles such that exactly one of control center i or control center j is inside the circle, and that's the answer.

https://codeforces.com/contest/33/submission/46096711

Why?

If both i and j are within a circle, there is no need to go over the fence. If they are both outside, there is no need. If exactly one of them is outside, they definitely need to go over that fence. O(MK)