Editorial for circles: Đường tròn

Hiểu bài toán

Bài toán yêu cầu tìm số phần tối đa mà n đường tròn có thể chia mặt phẳng. Nói cách khác, cho n (0 ≤ n ≤ 10^9), cần tính số vùng tối đa mà n đường tròn phân chia được.

• Ví dụ: 0 đường tròn -> 1 vùng; 1 đường tròn -> 2 vùng; 2 đường tròn -> 4 vùng; 3 đường tròn -> 8 vùng.
• Mặc dù các hình vẽ trong đề bài có thể khiến ta liên tưởng đến việc dùng đường thẳng (vùng maximum của n đường thẳng là (n^2 + n + 2)/2), nhưng đây là bài toán về đường tròn.
• Dựa trên các giải pháp được cung cấp, công thức tính là:
  • Nếu n = 0: Kết quả là 1.
  • Nếu n > 0: Kết quả là n^2 - n + 2.
• Ví dụ kiểm tra: n=3 -> 3^2 - 3 + 2 = 9 - 3 + 2 = 8. Điều này đúng với điều kiện các đường trôn xoắn (tương tự như đường tròn có bán kính vô hạn hoặc đường thẳng nhưng cuộn lại).

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

Cách Công thức trực tiếp

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n;
    cin >> n;
    if (n == 0) {
        cout << 1;
    } else {
        long long result = n * n - n + 2;
        cout << result;
    }
    return 0;
}

• Time Complexity: O(1)
• Space Complexity: O(1)

Đây là phương pháp hiệu quả nhất. Bài toán này thực chất là một bài toán quy nạp (recurrence relation) về hình học. Số vùng tối đa của n đường tròn (trong trường hợp này là path of circles hay circles in general position) được cho bởi công thức n^2 - n + 2 cho n >= 1. Với n = 0, số vùng là 1. Do n có thể lên tới 10^9, ta cần sử dụng kiểu dữ liệu 64-bit (long long) để tránh tràn số khi tính n^2.

Cách Quy hoạch động (Giả lập)

#include <iostream>
using namespace std;

int main() {
    long long n;
    cin >> n;
    if (n == 0) {
        cout << 1;
        return 0;
    }
    // Vòng lặp này chỉ mang tính chất minh họa logic quy hoạch động
    // không khả thi với n lớn (10^9) do độ phức tạp O(n)
    long long regions = 2; // Với 1 đường tròn
    for (long long i = 2; i <= n; ++i) {
        // Đường tròn thứ i cắt thêm 2*(i-1) phần
        regions += 2 * (i - 1);
    }
    cout << regions;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Phương pháp này dựa trên suy luận về quy hoạch động. Khi thêm đường tròn thứ k vào n-1 đường tròn cũ, đường tròn mới sẽ bị các đường tròn cũ cắt thành tối đa 2(k-1) đoạn. Mỗi đoạn này chia một vùng thành hai, do đó tăng số vùng lên 2(k-1). Từ đó suy ra công thức tổng quát: S(n) = S(n-1) + 2*(n-1). Tuy nhiên, với n lớn (10^9), cách này quá chậm để chạy hết vòng lặp, nên chỉ dùng để hiểu công thức.

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

Bài học kinh nghiệm

• Công thức chính xác cho bài toán này là 1 nếu n=0, và n^2 - n + 2 nếu n > 0.
• Lưu ý về kiểu dữ liệu: n có thể lên tới 10^9, nên n*n có thể lên tới 10^18. Cần dùng long long (hoặc unsigned long long) trong C++ để lưu trữ kết quả.

Lỗi thường gặp

• Quên xử lý trường hợp n = 0 (đề bài yêu cầu 0 ≤ n).
• Sử dụng kiểu int dẫn đến tràn số khi tính n*n với n lớn.