### Problem Link :

### Author : Smit mandavia

### Tester : Misha Chorniy

### Editorialist : Anand Jaisingh

### Pre-Requisites :

Basic Geometry

### Problem :

For N circles on the 2-d co-ordinate planes, you need to find the minimum and maximum distances between 2 points one from each circle, and then answer some queries.

### Explanation :

First of all, this problem was only for Division 2, but IMO this problem is much better than some of the problems that were only in Division 1. So, don’t feel too bad if you couldn’t solve this problem.

Basic knowledge of circles and lines is required to solve this problem. First of all, it may be evident from the constraints that we cannot process each K individually for each pair of circles. It may be much more profitable to do some kind of pre-processing so that we can later answer queries in something like O(1) or O(log_{2} (N^2) ) .

Let’s try and think of a single pair of circles for a moment, and forget everything else.Take a pair of points having maximal distance between them , one from the first circle, the other from the second.Now, take the pair of points where is distance is minimal

Taking any pair of points that are not equal to any of these 2 pairs, we know that the distance between them can only lie in the closed interval [minima,maxima]. In fact, if can be proved that for each real x, such that x lies in the interval [minima,maxima] there exists a pair of points having distance between them equal to x.

Now, if we can find the minima and maxima of the distances for 2 circles, then we can answer queries rather easily.

However, to do the former requires some case processing :

Big Hint : Try and draw a line passing through the centers of both circles, and analyzing this will lead you to all answers. In fact, it can be proved that the maxima is always the **sum of the distance between the centers of the 2 circles and their radii**. For example, consider :

Here, the length of segment FC is the radius of the inner circle, the length of segment CA is the distance between the centers of the 2 circles, and the length of segment AE is the radius of the outer circle.

So, |FE| = |FC|+|CA|+|AE|

We can prove this similarly for the cases when the circles only partially intersect, or don’t intersect at all. Now, for the minima, cases :

A. : The two circles share no common points

The minima in this case is the distance between the centers of the 2 circles minus the sum of their radii.

B. : A part of each of the circle intersects with the other

The minima here is obviously 0 as the 2 circles share at least 1 common point

C. : One of the circles lies completely inside or on the boundary of the other circle.

This is a tricky case. Here it’s the radius of the larger circle-(radius of the smaller circle + distance between the centers of the 2 circles). We can prove this as follows :

Let the radius of the outer circle be r. Any point on the outer circle’s circumference is at exactly a distance of r from the center of the outer circle. Now, if we can find the most distant point on the circumference of the **inner circle** from the center of the outer circle, then we can subtract that distance from r to get what we want. Now, that maximum distance is the distance between the centers of the 2 circles + the radius of the inner circle.

We can visualize this via the following image :

Here, point F is the most furthest point from point A, and the length of segment AF is length of segment AC i.e distance between the centers + length of segment CF i.e the radius of the inner circle. Now, length of segment i.e. |FE|=r-|AF| .

Now, to find if 2 circles intersect, overlap completely or don’t intersect at all is a problem that has appeared before. You can solve this problem to understand this part, and read the problem’s editorial if necessary.

Now, for a pair of circles once we found the maxima and minima, for each integer x such that x lies in the interval [minima,maxima], we can increment the answer for x by 1. However, to prevent looping, we can use the answer[minima]++, answer[maxima+1]-- trick since we can answer all queries offline.

Later, we can just print answer[k] in O(1). Overall time complexity : O(N^2+maxK+Q), where maxK=10^6.