
ZOJ Problem Set  3825
There is a beautiful garden in Marjar University. Recently, Edward, the headmaster of Marjar University, decided to build a garden water sprinkler system. The system consists of three sprinklers. Assuming that Marjar University is an infinite plane, the garden is a circle whose center is at (X_{0}, Y_{0}) with radius R. Now, Edward has already determined the position for two sprinklers at (X_{1}, Y_{1}) and (X_{2}, Y_{2}). He needs to choose the position for the last sprinkler. Here are some conditions to be satisfied:
Under these conditions, Edward wants to know the number of possible positions for the last sprinkler. Please write a program to help him! InputThere 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 S (1 <= S <= 10^{8}). The next line contains three integers X_{0}, Y_{0} and R (1 <= R <= 10^{8}). The last line contains four integers X_{1}, Y_{1}, X_{2} and Y_{2}. It is guaranteed that the absolute value of all input coordinates will not exceed 10^{8} and the positions of the two existing sprinklers are different. OutputFor each test case, output the number of possible positions. Sample Input1 4 0 0 4 1 0 1 0 Sample Output14 HintIn the sample test case, the possible positions for the last sprinkler are: (3, 2), (2, 2), (1, 2), (0, 2), (1, 2), (2, 2), (3, 2), (3, 2), (2, 2), (1, 2), (0, 2), (1, 2), (2, 2), (3, 2). Author: Lin, Xi Source: The 2014 ACMICPC Asia Mudanjiang Regional Contest 