java 円の中に辺1の正方形が存在する数の求めるアルゴリズム

Question

問題は
格子状に区切られた平面の、各格子は一辺が長さ1 の正方形です。
平面を区切る縦線と横線が交差しできる点のうち、適当な一点を中心として半径 r の円をその平面上に描き、内部を黒で塗りつぶします。

このとき一部でも黒で塗られている格子の数を出力するプログラムを作成してください。

例えば
r=1.7だとしたら、格子の数は16
r=100.02651だとしたら、格子の数は31852
r は0.00001 刻みで与えられる。

いろいろ調べて格子点を数える問題は何個かあり、高校生程度の問題と書いてありましたが、よく理解できませんでした。
１から詳しく説明していただきたいです。

どうぞよろしくお願い致します。

Answer 1

原点を中心とする円の方程式が分かればできるので、高校生程度の問題でしょう。

import java.util.Scanner;

class Test {
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for (;;) {
			System.out.print("r: ");
			if (!sc.hasNextDouble()) break;
			double r = sc.nextDouble();
			int sum = 0, n = (int)r;
			for (int i = 0; i <= n; i++)
				sum += (int)Math.ceil(Math.sqrt(r*r - i*i));
			System.out.println(sum * 4);
		}
		sc.close();
    }
}

実行例

r: 1.7
16
r: 100.02651
31852
r: .

追記
r = 1.0 の場合、結果が 4 になって欲しいのにそうならないのは、
切り上げをちゃんとしなかったからということで、コードを修正しました。

Comments

[kinako_make]

早速、ありがとうございます。
おかげで問題は解けました！
原点を中心とする円の方程式で調べたら、なんとなくですが何をしているかわかりました。