c049 - 00356 - Square Pegs And Round Holes
題目描述
題目要求計算在一個 2n x 2n 的棋盤上，以棋盤中心為圓心，半徑為 n-0.5 的圓形區域內，有多少個格子與圓有交集（部分包含在圓內），以及有多少個格子完全包含在圓內。
解題思路
題目採用暴力解法，遍歷棋盤上的每個格子，判斷其中心點到圓心的距離是否小於或等於圓的半徑。如果小於等於，則該格子被視為部分包含在圓內。如果格子的四個角都包含在圓內，則該格子被視為完全包含在圓內。由於題目 n 的範圍較小 (n <= 150)，因此暴力解法可以通過所有測試案例。計算部分包含的格子數時，先計算所有小於等於半徑的格子數，再減去完全包含的格子數，乘以 4 得到部分包含的格子數。
複雜度分析
- 時間複雜度: O(n^2)
- 空間複雜度: O(1)
程式碼
#include <iostream>
using namespace std;
int n;
int main(){
bool a=0;
while(cin >> n){
if(a)cout << "\n";
a=1;
int ans1=0,ans2=0;
float nn=(n*2.0-1)/2.0;
nn*=nn;
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
if(i*i+j*j<=nn)
++ans1;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i*i+j*j<=nn)
++ans2;
cout << "In the case n = " << n << ", " << (ans1-ans2)*4 << " cells contain segments of the circle.\nThere are " << ans2*4 << " cells completely contained in the circle.\n";
}
}