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 (X0, Y0) with radius R. Now, Edward has already determined the position for two sprinklers at (X1, Y1) and (X2, Y2). 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!
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 S (1 <= S <= 108). The next line contains three integers X0, Y0 and R (1 <= R <= 108). The last line contains four integers X1, Y1, X2 and Y2.
It is guaranteed that the absolute value of all input coordinates will not exceed 108 and the positions of the two existing sprinklers are different.
For each test case, output the number of possible positions.
1 4 0 0 4 -1 0 1 0
In 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 ACM-ICPC Asia Mudanjiang Regional Contest