Hiểu bài toán

Cho một hình vuông lớn có kích thước $2N \times 2N$ được chia thành các ô vuông nhỏ. Ta vẽ một đường tròn tâm tại $(N, N)$ và bán kính $R = N - 0.5$. Với mỗi $N$, cần tính:

1. Số ô vuông nhỏ bị đường tròn cắt (một phần ô nằm trong và một phần nằm ngoài).
2. Số ô vuông nhỏ nằm hoàn toàn bên trong đường tròn.

Vì hình tròn đối xứng qua trục hoành và trục tung, ta chỉ cần xét các ô vuông trong phần tư thứ nhất (từ $x=0$ đến $N-1$, $y=0$ đến $N-1$) rồi nhân đôi kết quả cho các phần tư còn lại. Tuy nhiên, do các trục $x=0$, $y=0$ và $x=N$ (với $N>0$) cũng thuộc vùng đối xứng, ta cần xử lý cẩn thận hoặc chỉ xét ô vuông trong vùng $0 \le x, y < N$ và nhân 4 (vì có 4 phần tư tương tự nhau).

Các cách tiếp cận

Cách Brute Force (Mô phỏng chi tiết)

#include <iostream>
#include <cmath>

using namespace std;

void solve() {
    int N;
    cin >> N;
    if (N == 0) {
        cout << "0 0\n";
        return;
    }
    double R = N - 0.5;
    long long inner_cnt = 0;
    long long cut_cnt = 0;

    // Duyệt qua từng ô vuông trong phần tư thứ nhất
    // Tọa độ ô vuông: [i, i+1] x [j, j+1]
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            // Tọa độ 4 góc của ô vuông
            double x1 = i, y1 = j;
            double x2 = i + 1, y2 = j;
            double x3 = i, y3 = j + 1;
            double x4 = i + 1, y4 = j + 1;

            // Kiểm tra xem các góc có nằm trong đường tròn không
            bool d1 = (x1*x1 + y1*y1 <= R*R);
            bool d2 = (x2*x2 + y2*y2 <= R*R);
            bool d3 = (x3*x3 + y3*y3 <= R*R);
            bool d4 = (x4*x4 + y4*y4 <= R*R);

            int cnt = d1 + d2 + d3 + d4;

            // Nếu cả 4 góc đều trong -> ô nằm hoàn toàn trong
            if (cnt == 4) {
                inner_cnt++;
            } 
            // Nếu có góc trong và không phải tất cả đều trong -> ô bị cắt
            else if (cnt > 0) {
                cut_cnt++;
            }
        }
    }

    // Kết quả là số ô trong 4 phần tư
    cout << cut_cnt * 4 << " " << inner_cnt * 4 << endl;
}

int main() {
    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

• Time Complexity: O(N^2) mỗi test case
• Space Complexity: O(1)

Giải pháp này mô phỏng trực tiếp quá trình vẽ. Với mỗi ô vuông trong phần tư thứ nhất (kích thước $N \times N$), ta kiểm tra tọa độ 4 góc của nó. Nếu tất cả 4 góc đều nằm trong đường tròn, ô đó được tính là 'nằm hoàn toàn trong'. Nếu chỉ có một số góc nằm trong (nhưng không phải tất cả), ô đó được tính là 'bị cắt'. Nếu không có góc nào nằm trong, ô đó nằm ngoài (trừ trường hợp đường tròn bao trọn ô mà không qua góc nào, nhưng với bán kính $N-0.5$ thì điều này không xảy ra cho các ô nằm ngoài vùng). Kết quả thu được từ phần tư này sẽ được nhân với 4 để có đáp án cho toàn bộ hình vuông.

Cách Quy hoạch động / Duyệt theo hàng

// Solution 2 & 3 essentially use this approach
#include <iostream>
#include <cmath>

using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int N;
        cin >> N;
        if (N == 0) {
            cout << "0 0\n";
            continue;
        }

        double R_sq = (N - 0.5) * (N - 0.5);
        int xanh = 0; // Hoàn toàn trong
        int red = 0;  // Bị cắt

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                int x1 = i,     y1 = j;
                int x2 = i + 1, y2 = j;
                int x3 = i,     y3 = j + 1;
                int x4 = i + 1, y4 = j + 1;

                bool d1 = (x1*x1 + y1*y1 <= R_sq);
                bool d2 = (x2*x2 + y2*y2 <= R_sq);
                bool d3 = (x3*x3 + y3*y3 <= R_sq);
                bool d4 = (x4*x4 + y4*y4 <= R_sq);

                int cnt = d1 + d2 + d3 + d4;
                if (cnt == 4) {
                    xanh++;
                } else if (cnt > 0) {
                    red++;
                }
            }
        }
        cout << red * 4 << " " << xanh * 4 << endl;
    }
    return 0;
}

• Time Complexity: O(N^2) mỗi test case
• Space Complexity: O(1)

Đây là cách tiếp cận tối ưu hóa trực quan từ brute force. Thay vì dùng số thực double cho các phép tính diện tích, ta chỉ cần tập trung vào logic:

1. Bán kính hiệu dụng là $R = N - 0.5$. Vì vậy, một điểm $(x, y)$ nằm trong đường tròn nếu $x^2 + y^2 \le (N - 0.5)^2$.
2. Ta chỉ xét các ô vuông trong phần tư thứ nhất ($0 \le x, y < N$).
3. Với mỗi ô vuông tại $(i, j)$, tính xem bao nhiêu góc nằm trong:
   • 0 góc: Ô nằm ngoài.
   • 4 góc: Ô nằm hoàn toàn trong.
   • 1, 2, hoặc 3 góc: Ô bị cắt.
4. Kết quả là tổng số ô của mỗi loại trong phần tư nhân với 4.

Lưu ý: Các giải pháp mẫu đều dùng double cho $R$ và phép tính bình phương. Trong C++ với số nguyên nhỏ, có thể dùng số nguyên thuần túy: $R^2 = (2N-1)^2 / 4$. Điều này tránh sai số số học.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Tính đối xứng: Thay vì xét toàn bộ lưới $2N \times 2N$, ta chỉ cần xét $N \times N$ ô vuông trong phần tư thứ nhất và nhân 4.
• Định nghĩa 'Bị cắt': Một ô vuông bị đường tròn cắt khi có ít nhất một góc nằm trong đường tròn nhưng không phải tất cả các góc đều nằm trong.
• Bán kính hiệu dụng: Vì đường tròn đi qua trung điểm của các cạnh của lưới ô li (tọa độ $N, N, N-1, ...$), bán kính hiệu dụng để kiểm tra các góc là $N - 0.5$. Điều này đảm bảo các ô vuông ở biên $x=N$ hoặc $y=N$ (nếu có) sẽ được xử lý chính xác. Với $N>0$, các ô vuông tại $x=N$ (vùng thứ hai) về mặt logic tương đương với $x=N-1$ nhưng ta chỉ cần xét $0 \le i, j < N$.

Lỗi thường gặp

• Sai số số học khi dùng số thực (double): Việc so sánh trực tiếp số thực có thể dẫn đến sai lệch (ví dụ: 3.9999999 < 4.0). Nên chuyển đổi sang dùng số nguyên (tính bình phương bán kính là $((2N-1)^2)/4$) hoặc dùng số thực cẩn thận với sai số cho phép.
• Xử lý biên sai: Nếu dùng $R = N$, các ô tại biên $x=N$ hoặc $y=N$ có thể bị đếm sai. Phải dùng $R = N - 0.5$ hoặc $R = N - 1e-9$.
• Quên trường hợp $N=0$: Khi $N=0$, lưới rỗng, đáp án là 0 0.