ZeroJudge 解題筆記：c049. 00356 - Square Pegs And Round Holes

作者：王一哲
日期：2026年2月9日


ZeroJudge 題目連結：c049. 00356 - Square Pegs And Round Holes

解題想法

先算數學，如果正方形的邊長為 $n$，則圓的半徑為 $r = 0.5 \times (2n - 1)$。接下來用兩層 for 迴圈掃過正方形的右上角每一格，假設正方形正中央為原點 $(0, 0$)，格子座標的左下角 $(x, y)$，如果 $(x+1)^2 + (y+1)^2 \leq r^2$ 代表這格在圓之中，如果 $x^2 + y^2 > r^2$ 代表這格在圓之外，再將計算結果乘以 4 就是對應的答案 $inner$ 及 $outer$，圓上的格子數則是 $4n^2 - outer - inner$。

Python 程式碼

使用時間約為 1.2 s，記憶體約為 3.3 MB，通過測試。

import sys

first = True
for line in sys.stdin:
    if not first: print()
    first = False
    n = int(line)
    r = (2*n - 1) * 0.5
    inner, outer = 0, 0
    for x in range(n):
        for y in range(n):
            if (x+1)**2 + (y+1)**2 <= r*r: inner += 1
            elif x**2 + y**2 > r*r: outer += 1
    inner *= 4; outer *= 4
    print(f"In the case n = {n:d}, {4*n*n-outer-inner:d} cells contain segments of the circle.")
    print(f"There are {inner:d} cells completely contained in the circle.")

使用時間約為 1.2 s，記憶體約為 3.4 MB，通過測試。

import sys

lines = sys.stdin.readlines()
result = []
first = True
for line in lines:
    if not first: result.append("\n")
    first = False
    n = int(line)
    r = (2*n - 1) * 0.5
    inner, outer = 0, 0
    for x in range(n):
        for y in range(n):
            if (x+1)**2 + (y+1)**2 <= r*r: inner += 1
            elif x**2 + y**2 > r*r: outer += 1
    inner *= 4; outer *= 4
    result.append(f"In the case n = {n:d}, {4*n*n-outer-inner:d} cells contain segments of the circle.\n")
    result.append(f"There are {inner:d} cells completely contained in the circle.\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 3 ms，記憶體約為 76 kB，通過測試。

#include <cstdio>

int main() {
    bool first = true;
    int n;
    while(scanf("%d", &n) != EOF) {
        if (!first) puts("");
        first = false;
        float r = (2.0*n - 1.0) * 0.5;
        int inner = 0, outer = 0;
        for(int x=0; x<n; x++) {
            for(int y=0; y<n; y++) {
                if ((x+1.0)*(x+1.0) + (y+1.0)*(y+1.0) <= r*r) inner++;
                else if (1.0*x*x + 1.0*y*y > r*r) outer++;
            }
        }
        inner *= 4; outer *= 4;
        printf("In the case n = %d, %d cells contain segments of the circle.\n", n, 4*n*n-outer-inner);
        printf("There are %d cells completely contained in the circle.\n", inner);
    }
    return 0;
}