Problem E
Mushroom Misery
Input: Standard Input
Output: Standard Output
Time Limit: 2 Seconds
The Institute of Ubiquitousness in
Lichtenstein, LIU, conducts a project where the effect of a special type of
fungi, sphera carnelevarium, is studied. This fungus is very special, since it
grows in a circular fashion from its centre, without interference from other
objects or other individuals.
Until
now, the impact of this forest-living creature has been measured by examining a
grid consisting of n*n squares of size 1 m2. A grid is
considered affected, if fungi are present in the square, otherwise it is
considered clean. Grids, where the fungus merely touches the border of the square
are not considered affected.
Of course, the task of examining grids is tedious and now unnecessary, since Prof. Muggel discovered that the grow rate is exactly 2.718281828 m/day. Now, counting the number of affected squares should be like a stroll in the park, right? Since there are a lot of old data, which will be compared to the new data, the rules of counting the squares must be the same. Do not use data types with unnecessary low precision in your calculations.
Fig: This figure corresponds to the sample input
Input
On
the first line of input there is one integer, N <= 10, giving the
number of test cases in the input. After this line, N test cases
follows. Each test case starts with a line containing two integers size,
n
such that 0 < size <= 1000000, 0 < n
<= 1000, where size is the size of the grid in meters and n is
the number of individuals in the test grid. After this line, n lines
follows, each line consisting of three
decimal number, 0 <= x <= size, 0 <= y <= size, 0
< r<= size, where x and y are the zero-based
coordinates of the center of the individual and r is the (estimated)
radius in meters.
Output
For every test case, output one line containing the number of affected squares (a number between 0 and size2). However, the number of affected squares is always less than 1000000000 (109).
Sample
Input Output for Sample Input
|
2 1 2 3 1 1.5 1.5 0.44 5 3 2 2 1.31 1.5 2.5 0.5 3 3 0.94 |
1 13 |