题目描述一个直径为2 n − 1 2n - 12n−1单位的圆被绘制在2 n × 2 n 2n \times 2n2n×2n的棋盘上。下图展示了n 3 n 3n3时的构造。要求编写程序确定棋盘上包含圆弧段的格子数量以及完全位于圆内的格子数量。输入格式输入文件的每行包含一个不超过150 150150的正整数n nn。输出格式对于每个输入值n nn按样例输出格式输出两行后跟一个空行。样例输入3 4样例输出In the case n 3, 20 cells contain segments of the circle. There are 12 cells completely contained in the circle. In the case n 4, 28 cells contain segments of the circle. There are 24 cells completely contained in the circle.题目分析问题的本质这是一个几何计数问题。圆被放置在2 n × 2 n 2n \times 2n2n×2n的棋盘中央圆的直径d 2 n − 1 d 2n - 1d2n−1因此半径为r ( 2 n − 1 ) / 2 n − 0.5 r (2n - 1)/2 n - 0.5r(2n−1)/2n−0.5。棋盘共有( 2 n ) × ( 2 n ) (2n) \times (2n)(2n)×(2n)个单元格每个单元格是1 × 1 1 \times 11×1的正方形。圆与棋盘同中心。坐标系统将棋盘左下角设为( 0 , 0 ) (0,0)(0,0)右上角为( 2 n , 2 n ) (2n, 2n)(2n,2n)。每个单元格以其左下角坐标( i , j ) (i, j)(i,j)标识其中0 ≤ i , j ≤ 2 n − 1 0 \le i, j \le 2n-10≤i,j≤2n−1。圆的中心位于( n , n ) (n, n)(n,n)半径为r n − 0.5 r n - 0.5rn−0.5。单元格分类完全在圆内单元格的四个顶点都在圆内到圆心距离≤ r \le r≤r包含圆弧段与圆相交单元格至少有一个顶点在圆内至少有一个顶点在圆外且该单元格与圆相交对称性由于圆和棋盘都是中心对称的只需计算四分之一的区域然后乘以4 44。参考代码// Square Pegs And Round Holes// UVa ID: 356// Verdict: Accepted// Submission Date: 2016-06-28// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){intn,cases0;while(cinn){// 输出空行分隔测试用例if(cases)coutendl;// 包含圆弧段的格子数 (2n-1) * 4coutIn the case n n, (2*n-1)*4;cout cells contain segments of the circle.endl;// 统计完全位于圆内的格子数intcontained0;// 只考虑第一象限不含坐标轴因为对称性for(inti1;in-1;i)for(intj1;jn-1;j)// 判断右上角顶点是否在圆内// 等价于 4(i^2 j^2) (2n-1)^2if(4*(i*ij*j)(2*n-1)*(2*n-1))contained;// 四个象限乘以 4coutThere are contained*4 cells completely contained in the circle.endl;}return0;}