D - Circle Lattice Points Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

2 次元平面上に中心 (X, Y) 、半径 R の円があります。
この円の内部または周上にある格子点 (x, y 座標がともに整数である点) の個数を求めてください。

制約

  • |X| \le 10^5
  • |Y| \le 10^5
  • 0 \lt R \le 10^5
  • X, Y, R は高々小数第 4 位まで与えられる

入力

入力は以下の形式で標準入力から与えられる。

X Y R

出力

答えを出力せよ。

入力例 1

0.2 0.8 1.1

出力例 1

3

以下のような円になります。赤く印の付いた点が、この円の内部または周上にある格子点です。
グラフ

入力例 2

100 100 1

出力例 2

5

X, Y, R には小数点が含まれないかもしれません。
円周上の格子点も数える対象に含むことに注意してください。

入力例 3

42782.4720 31949.0192 99999.99

出力例 3

31415920098

Score : 400 points

Problem Statement

We have a circle of radius R centered at (X, Y).
Find the number of grid points (points whose x- and y-coordinates are both integers) within or on the circle.

Constraints

  • |X| \le 10^5
  • |Y| \le 10^5
  • 0 \lt R \le 10^5
  • Each of X, Y, and R has at most four digits after the decimal point.

Input

Input is given from Standard Input in the following format:

X Y R

Output

Print the answer.

Sample Input 1

0.2 0.8 1.1

Sample Output 1

3

The circle is shown below. The grid points within or on the circle are marked red.

Figure

Sample Input 2

100 100 1

Sample Output 2

5

X, Y, and R may not have decimal points. Note that we also count the grid points on the circle.

Sample Input 3

42782.4720 31949.0192 99999.99

Sample Output 3

31415920098