正方形のチップ [DISCO presents ディスカバリーチャンネル コードコンテスト2016 本戦 A]
右上の領域の正方形の数を数えてから、4倍して答えを求めます。
「右上の領域にある正方形」が円に含まれているかどうかは、正方形の右上の頂点が円に含まれているかどうかということに等しいです。よって、右上の頂点に注目して数えていくことにします。探索する範囲は、 R * R の正方形の範囲で十分です。
右上の頂点が円に含まれているかどうかは、「右上の頂点の座標と原点との距離が、ユークリッド距離で R 以下であるか」によって判定します。以下というところが重要で、仮に右上の頂点が円周上にあったとしても、正方形を切り出すことができます。
import java.util.*; class Main { static Scanner sc = new Scanner(System.in); public static void main(String[] args) { int r = sc.nextInt(), c = sc.nextInt(); int ans = 0; for (int i=c; i<r; i+=c) { for (int j=c; j<r; j+=c) { if (calcEuclidDistance(0,0,(double)i,(double)j) <= r) ans++; } } System.out.println(ans*4); } static double calcEuclidDistance (double x1, double y1, double x2, double y2) { double d = Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)); return d; } }
for文の i+=c, j+=c という書き方はあまり使わないので、いい練習になりました。