Circles on a Screen

Time limit3sMemory limit256 MB

Summary

Given up to 100 circles drawn on a w×h grid, count how many pixels remain black after the union of circles is painted white.

Level: Medium5 of 10
Topics: Geometry, Simulation, Implementation
Solved: No attempts yet

Problem

Andrew wrote a program that draws $n$ white circles on a black screen. The screen is monochrome and has a resolution of $w \times h$ pixels. Pixels are numbered from the upper-left corner $(0, 0)$ to the bottom-right corner $(w-1, h-1)$ .

A circle with its center at pixel $(x_c, y_c)$ and radius $r$ consists of every pixel $(x, y)$ such that $\sqrt{(x_c - x)^2 + (y_c - y)^2} \le r$ . If a circle does not fit on the screen, the part that falls outside is cut off. A pixel that belongs to at least one circle is white.

Andrew liked the resulting picture and wants to copy it onto his wall. The wall is white and he can only paint some pixels black, so he needs to know how much black paint he will use. He copies the picture exactly, pixel by pixel. Write a program that counts how many black pixels remain on the screen after all $n$ circles have been drawn.

Input

The first line contains three integers $w$ , $h$ , and $n$ ( $1 \le w, h \le 20\,000$ ; $1 \le n \le 100$ ). Each of the next $n$ lines describes one circle with three integers $x_i$ , $y_i$ , and $r_i$ ( $0 \le x_i < w$ ; $0 \le y_i < h$ ; $0 \le r_i \le 40\,000$ ): a circle centered at pixel $(x_i, y_i)$ with radius $r_i$ .

Output

Output a single integer: the number of black pixels that remain on the screen.

Hint

The illustration above corresponds to the second example.

Examples2

Example 1
Input
```
5 3 2
1 1 1
3 1 1
```
Expected output
```
6
```
Example 2
Input
```
12 9 2
3 3 2
7 5 4
```
Expected output
```
51
```