Marcus is replacing the flooring in his kitchen. The new floor is made up of small square lineoleum tiles which
may be either white or black. The tiles are arranged in a tight grid. He names the center tile the "origin tile",
and specifies that the lower-left corner of this tile is located at (0, 0). Each tile is named by the
coordinate of its lower-left corner.
Marcus wants the floor to be completely white, except for a large black circle surrounding an island in the kitchen.
The center of the circle must be at position (Cx, Cy) and have radius R. Because the island is a fixed size, and
the tiles are only manufactured in a single size, the circle does not align well to the grid and the values of
Cx, Cy, and R are decimals, not integers.
Additionally, Marcus wonders how he should best draw a circle using only square tiles. He decides to use the following method:
- First, he places white tiles onto the entire floor.
- Then, he draws the desired circle with a pencil onto the tiles.
- Finally, he replaces any white tile having a pencil mark with a black tile.
Problem Statement
You will be asked to calculate the black tiles required to make the circle using the above method.
To allow answers to be short, report the sum of each x and y coordinate of each black tile as
a single integer value.
For example, the circle having centerpoint (5.8, 5.1) and radius 0.793 passes over the following tiles:
(5, 5)
(6, 5)
(6, 4)
(5, 4)
The total sum of the above eight integers is 40, which would be the expected answer.
Here is a visualization of a larger example, where (Cx, Cy) = (6.5, 7.6) and R = 5.957.
Input Data
First line will be Q, the quantity of testcases.
Q lines will then follow, each with three space-separated values Cx Cy R.
Answer
Should consist of Q space-separated integers, corresponding to the sum of the coordinates of each black tile
required to create the described circle in each testcase.
Example
input data:
4
5.8 5.1 0.793
5.5 -5.5 0.793
6.4 7.6 5.957
-915.3 -891.1 975.937
answer:
40 -8 624 -14114528