Pennies in the Ring

Time limit1sMemory limit128 MB

Summary

Count integer lattice points inside or on a circle of given radius for each radius until a 0 terminates input.

Level: Medium4 of 10
Topics: Math, Geometry, Brute force
Solved: No attempts yet

Problem

The game “Pennies in the Ring” is often played by bored programmers who have grown tired of solitaire. The goal is to see how many pennies can be placed inside a circle. The circle is drawn on a grid, with its center at the coordinate $(0, 0)$ . A single penny is placed on every integer grid coordinate (for example $(1, 1)$ , $(1, 2)$ , and so on) that lies inside or on the circle. It is not a very exciting game, but it is great for wasting time. Given a radius, compute how many pennies are needed to fill the circle.

Input

The input is a sequence of positive integers, one per line, where each integer is the radius of a circle. Each radius is at most $25000$ . The end of the input is marked by a single $0$ on its own line. You may assume the grid is large enough that two pennies on adjacent integer coordinates never touch.

Output

For each circle, output on its own line the number of pennies it needs. Do not output anything for the terminating $0$ . You may assume the number of pennies for any circle is fewer than $2$ billion (which is only $20 million dollars: computer scientists have lots of money).

Examples4

Example 1
Input
```
2
3
4
0
```
Expected output
```
13
29
49
```
Example 2
Input
```
1
0
```
Expected output
```
5
```
Example 3
Input
```
5
0
```
Expected output
```
81
```
Example 4
Input
```
1
2
3
4
5
0
```
Expected output
```
5
13
29
49
81
```