a672 - 00155 - All Squares
題目描述
題目要求計算給定座標 (x, y) 落在多少個嵌套的正方形中。最大的正方形邊長為 2k+1，中心位於 (1024, 1024)。較小的正方形以其父正方形的四個角為中心，邊長為父正方形邊長的一半。輸入為正方形的大小 k 和座標 (x, y)，輸出座標被包含的正方形的數量。
解題思路
程式碼使用迭代的方式模擬正方形的嵌套結構。從最大的正方形開始，檢查給定的座標是否在其範圍內。如果座標在範圍內，則計數器加一。然後，將正方形的大小減半，並移動到下一個正方形的中心位置。這個過程重複進行，直到正方形的大小變為 0。正方形的中心位置的更新方式是根據座標 (x, y) 相對於當前中心位置 (centerX, centerY) 的位置來決定的。如果當前中心位置小於給定的座標，則向正方向移動，否則向負方向移動。
複雜度分析
- 時間複雜度: O(log k)，其中 k 是輸入的正方形大小。因為正方形的大小每次迭代都會減半，所以迭代的次數與 log k 成正比。
- 空間複雜度: O(1)，程式碼只使用了常數個變數，因此空間複雜度為常數。
程式碼
#include <iostream>
#include <iomanip>
using namespace std;
int main(){
cin.sync_with_stdio(false), cin.tie(0);
int squareSize, x, y, leftBound, rightBound, topBound, bottomBound, centerX, centerY, counts;
while (cin >> squareSize >> x >> y, squareSize || x || y) {
counts = 0, centerX = centerY = 1024;
do {
if (centerX - squareSize <= x && x <= centerX + squareSize && centerY - squareSize <= y && y <= centerY + squareSize)
++counts;
centerX += (centerX < x ? squareSize : -squareSize);
centerY += (centerY < y ? squareSize : -squareSize);
squareSize >>= 1;
} while (squareSize);
cout << right << setw(3) << counts << '\n';
}
}