Counting Lit Pixels

Time limit1sMemory limit128 MB

Summary

For each integer circle center and radius, count the unit grid squares the disk covers, ignoring squares touched only along an edge or corner.

Level: Medium6 of 10
Topics: Math, Geometry, Binary search, Implementation
Solved: No attempts yet

Problem

On a 1080p high-definition display, drawing a circle that fills the screen lights up almost a million pixels — that's a lot of pixels! But exactly how many pixels are lit? Let's find out.

Model the display as a Cartesian grid in which every pixel is a unit square. For example, one pixel occupies the square whose opposite corners are $(0, 0)$ and $(1, 1)$ . A circle is described by its center in grid coordinates together with its radius, and it is drawn as a filled disk. A pixel is lit if any part of it is covered by the disk. A pixel that the circle only grazes along an edge or at a single corner is not lit.

Given the position and radius of a circle, compute the exact number of pixels it lights up.

Input

The input consists of several test cases, each on its own line. Each test case is three integers $x$ , $y$ , and $r$ ( $1 \le x, y, r \le 10^6$ ), giving the center $(x, y)$ and the radius $r$ of the circle. The input ends with a line containing 0 0 0, which must not be processed.

Output

For each test case, print on its own line the number of pixels that are lit when the specified circle is drawn. You may assume that the entire circle fits within the display area.

Examples3

Example 1
Input
```
1 1 1
5 2 5
0 0 0
```
Expected output
```
4
88
```
Example 2
Input
```
1 1 1
0 0 0
```
Expected output
```
4
```

Example 3

Input

Expected output