UVa 356 Square Pegs And Round Holes

题目描述

一个直径为2 n − 1 2n - 12n−1单位的圆被绘制在2 n × 2 n 2n \times 2n2n×2n的棋盘上。下图展示了n = 3 n = 3n=3时的构造。

要求：编写程序，确定棋盘上包含圆弧段的格子数量，以及完全位于圆内的格子数量。

输入格式

输入文件的每行包含一个不超过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 - 1d=2n−1，因此半径为r = ( 2 n − 1 ) / 2 = n − 0.5 r = (2n - 1)/2 = n - 0.5r=(2n−1)/2=n−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.5r=n−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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){intn,cases=0;while(cin>>n){// 输出空行分隔测试用例if(cases++)cout<<endl;// 包含圆弧段的格子数 = (2n-1) * 4cout<<"In the case n = "<<n<<", "<<(2*n-1)*4;cout<<" cells contain segments of the circle."<<endl;// 统计完全位于圆内的格子数intcontained=0;// 只考虑第一象限（不含坐标轴），因为对称性for(inti=1;i<=n-1;i++)for(intj=1;j<=n-1;j++)// 判断右上角顶点是否在圆内// 等价于 4(i^2 + j^2) <= (2n-1)^2if(4*(i*i+j*j)<=(2*n-1)*(2*n-1))contained++;// 四个象限，乘以 4cout<<"There are "<<contained*4<<" cells completely contained in the circle."<<endl;}return0;}