UAPSC Weekly Random Problem Assortment


2019-02-15 22:48 UTC

UAPSC Weekly Random Problem Assortment


2019-02-22 22:48 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -99 days 7:12:28

Time elapsed


Time remaining


Problem J
Mushroom Misery

The Institute of Ubiquitousness in Lichtenstein, LIU, conducts a project where the effect of a special type of fungi, sphera carnelevarium, are 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 \times n$ squares of size $1$ m$^2$. A grid square is considered affected if fungi are present in the square, otherwise it is considered clean. Grid squares 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. M├╝ggel 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.

\includegraphics[width=0.5\textwidth ]{fig1}
Figure 1: Illustrations of the two sample cases.


Input starts with a line containing two integers $s$ and $n$ such that $1 \le s \le 100\, 000$ and $0 \le n \le 100$, where $s$ 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 real numbers, $0 \le x \le s$, $0 \le y \le s$ and $0 < r \le s$ , where $x$ and $y$ are the zero-based coordinates of the centre of the individual and $r$ is the (estimated) radius in meters.

All real values are given with at most $10$ digits after the decimal point.


For every test case, output one line containing the number of affected squares (a number between $0$ and $s^2$).

You may assume that the input is such that increasing the radius of any mushroom by $10^{-6}$ meters would not change the answer.

Sample Input 1 Sample Output 1
3 1
1.5 1.5 0.44
Sample Input 2 Sample Output 2
5 3
2 3 1.31
1.5 2.5 0.5
3 2 0.94
Sample Input 3 Sample Output 3
10 1
4.42 0.23 0.5