CPC '21 Contest 1 P3 - AQT and Circles

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Python 4.0s
Memory limit: 256M

Problem types

AQT is studying circles and he has encountered the following problem. Two circles C_1 and C_2 have their centres located at (0,0) on a coordinate plane. Circle C_1 and C_2 have radii R_1 and R_2 (R_1 \le R_2), respectively. AQT decides to add another circle C_3 with radius R_3 (R_3 < R_2) and a centre that is located at (x,y), where x and y are real numbers. The location of circle C_3 is random but it follows the condition that it is completely inside circle C_2. Formally, x^2 + y^2 < (R_2-R_3)^2. A position of circle C_3 is called valid if the circumference of circle C_3 has 0 intersection points with the circumference of circle C_1. AQT wants to know the probability that the position of circle C_3 is valid. AQT is given T of these problems. Can you help AQT solve all of them?


In all subtasks,

1 \le T \le 2 \cdot 10^5

1 \le R_1 \le R_2 \le 10^3

1 \le R_3 < R_2

It is guaranteed that R_1, R_2, and R_3 are integers.

Subtask 1 [10%]

R_1 = R_2

Subtask 2 [15%]

0 \le R_2 - R_1 \le 2

R_3 < R_1

Subtask 3 [75%]

No additional constraints.

Input Specification

The first line contains T, the number of problems you need to help AQT solve.

The next T lines each contain the radii of the three circles: R_1, R_2, and R_3.

Output Specification

Output T lines. In the i-th line, output the answer to the i-th problem. Your answer will be considered correct if it differs from the correct answer by at most 10^{-3}.

Sample Input

2 3 1
5 10 2

Sample Output



For the first test case, circle C_1 and C_2 are represented by the blue circle and the red circle, respectively. The green circles represent possible valid positions for circle C_3.

This region represents the set of all possible centres for circle C_3 and has an area of 4\pi
This region represents the set of all valid centres for circle C_3 and has an area of \pi
The probability is \frac{\pi}{4\pi} = 0.25


There are no comments at the moment.