🔗 🟡 ABC389D Squares in Circle

Problem Statement

題目簡述

在二維座標平面上，有一個無限延伸的 $1 \times 1$ 正方形棋盤。以原點為圓心畫一個半徑為 $R$ 的圓，求有多少個正方形能被這個圓完全包含。換句話說，正方形的四個角與原點的距離都必須不超過 $R$ 。

Constraints

約束條件

$1 \leq R \leq 10^{6}$

思路：幾何 + 雙指標

題型定位

核心考點是在二維平面上統計滿足幾何條件的格子數量。如果直接枚舉圓附近所有可能的中心點，複雜度會到 $\mathcal{O}(R^2)$ ；而 $R$ 最大到 $10^6$ ，這條路走不通。

所以重點不是換一個更快的資料結構，而是先把幾何條件壓縮：利用圓的對稱性減少需要統計的區域，再利用邊界的單調性把二維枚舉降成線性掃描。

從對稱性拆解問題

圓關於 $X$ 軸與 $Y$ 軸對稱，棋盤本身也有同樣的對稱性。因此只要知道第一象限內有多少個符合條件的正方形，就能用對稱性推出其他象限的數量。

不過座標軸上的正方形不能直接混進象限裡一起乘以 $4$ ，否則會重複計算。因此先依照中心位置分成三類：

中心在圓心：由於 $R \geq 1$ ，此正方形必在圓內，固定 $1$ 個。
中心在座標軸上：正 $X$ 軸上有 $R - 1$ 個，四條半軸共 $4(R - 1)$ 個。
中心在象限內：由對稱性，只需計算第一象限的數量再乘以 $4$ 。

對稱性化簡

遇到圓、正方形網格、曼哈頓距離這類天然對稱的幾何計數題，可以先把特殊位置（原點、座標軸）單獨拿出來，再只處理一個象限。這樣既能降低討論量，也能避開重複計數。

第一象限的雙指標

接著只看第一象限。對於中心為 $(i, j)$ （ $i, j \geq 1$ ）的正方形，離原點最遠的角一定是右上角 $(i + 0.5, j + 0.5)$ 。只要這個角落在圓內，其餘三個角也一定在圓內。

因此，正方形完全在圓內等價於：

(i + 0.5)^2 + (j + 0.5)^2 \leq R^2

關鍵單調性

當橫座標往右移時， $(i + 0.5)^2$ 會變大。若仍要留在圓內，縱座標的上界只可能下降，不可能上升。也就是說，對每個橫座標而言，合法的最高位置是單調不增的，這正是雙指標能成立的原因。

做法就很自然了：從第一象限中可能的最高位置開始，橫座標從左到右掃過；如果當前位置超出圓，就把高度往下調，直到重新落回圓內。

此時，對於當前橫座標，從 $1$ 到目前高度的所有位置都合法，因為越往下距離原點越近。所以每一列的貢獻就是目前高度。把第一象限的貢獻加總後乘以 $4$ ，再加上原點與座標軸上的部分，就是答案。

可遷移模型：單調性驅動的雙指標

當一個維度增加時，另一個維度的合法邊界只會單向移動，就可以考慮用雙指標把 $\mathcal{O}(n^2)$ 的枚舉壓到 $\mathcal{O}(n)$ 。內層 while 迴圈看起來像是又跑了一層，但指標全程只會往同一個方向移動，因此總移動次數仍是線性的。

複雜度分析

時間複雜度： $\mathcal{O}(R)$ $O (R)$
- 外層枚舉 $i$ 需要 $\mathcal{O}(R)$ ，內層 $j$ 只會減少，總共最多減少 $R$ 次，均攤 $\mathcal{O}(1)$ 每次迭代。
空間複雜度： $\mathcal{O}(1)$

Code

R = int(input())

ans = 1 + 4 * (R - 1)  # 中心位於原點和座標軸上

j = R
for i in range(1, R + 1):
    # 檢查中心點座標為 (i, j) 的正方形其是否在圓內
    while j > 0 and (i + 0.5) * (i + 0.5) + (j + 0.5) * (j + 0.5) > R * R:
        j -= 1
    # 此時中心點為 (i, j), (i, j-1), ... (i, 1) 的正方形都在圓內
    ans += 4 * j  # 四個象限
print(ans)