ZOJ Problem Set - 3783
Edward has a lot of money. But he does not like paper currency. He exchanged all his money into coins. So he has many coins of different sizes and values. He likes to play games with his coins, which he called as the hobby of gentlemen.
This time, he created a new game with his coins. Being bored with flipping and tossing coins, he wanted to roll coins. He fixes several coins on a table and uses another coin to circle around the fixed coins. The rolling coin touches exactly one of the fixed coins initially.
Edward circles the coin around the initially-touched-coin clockwise until it touches another fixed coin. Then, Edward continued circling it around the newly touched coin. This will be proceeded until the coin moves back to the initial place.
Edward likes the curve drawn by the circling coin. He wants to know the total angle that the coin had circled. Can you help him with this problem?
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
The first line contains an integer N (1 <= N <= 1000), indicating the number of fixed coins.
The following N + 1 lines, each line contains 3 numbers X, Y and R, describing the coordinates and the radius of a coin. The first N lines each describes a fixed coin, while the last one describes the rolling coin.
The absolute value of each coordinate does not exceed 10000 and the radius of each coin lies between 1 and 100, inclusive. It is guaranteed that no two coins overlap and that the rolling coin touches exactly one fixed coin initially.
For each case, output the total angle the coin rolls when it returns to the initial place. Any solution with a relative or absolute error of at most 1e-6 will be accepted.
2 1 0 0 1 -2 0 1 2 -1 0 1 1 0 1 -1 2 1
Author: GUAN, Yao
Source: The 11th Zhejiang Provincial Collegiate Programming Contest