A lattice point is a point (x,y) in the 2-dimensional xy-plane with x,y ∈ Z, where Z be the set of integers. Let P (r) = {(x, y)|x2 + y2 ≤ r2, (x, y) is a lattice point in the xy-plane} and we denote D(r) be the number of elements in P(r). For each lattice point (x,y) in the xy-plane, let and S(x, y) = {(u, v)|x ≤ u ≤ x + 1, y ≤ v ≤ y + 1} B(r) = {(x, y)|x2 + y2 ≤ r2, x and y are real numbers} √ Then it is easy to verify that when r > √∪√ We know that Area (x,y)∈P (r) Hence This implies It yields S(x, y) = Area(S(x, y)) = (x,y)∈P (r) √√ π(r− 2)2 <D(r)<π(r+ 2)2 1 = D(r). (x,y)∈P (r) B(r− 2)⊂ 2 (x,y)∈P (r) S(x,y)⊂B(r+ 2) ∪∑∑ ( √ )2 ( √ )2 π 1− 2 <D(r)<π 1+ 2 rr2 r lim D(r) = π r→∞ r2 So if we can calculate D(r) for a large r, then we can estimate the value of π. The following C function can be used to calculate the value of D(r) withing a reasonable aumount of time when r is a small integer, say e.g., 1 ≤ r ≤ 10, 000. long D(long r) { } Is is easy to obtained D(1) = 5, D(2) = 13, D(3) = 29, and D(10000) = 314159053 using this program. Recall that π = 3.14159.... Your task is to find D(r) for a large r within a reasonable amount of time. long x,y,count=0; for(x=-r;x<=r;x++) for(y=-r;y<=r;y++) if(xx+yy<=r*r) count++; return count;
2/2 Input There are multiple lanes in the input file, the k-th line contain an integer nk (1 ≤ nk ≤ 100, 000, 000). Output List integer nk in line 2k − 1 and the value of D(nk) in line 2k for k = 1,2,3,4,5,... Sample Input 1 2 3 10000 100000000 Sample Output 1 5 2 13 3 29 10000 314159053 100000000 31415926535867961