Hiểu bài toán

Cho ~n~ điểm phân biệt trên mặt phẳng. Yêu cầu đếm số đoạn thẳng có độ dài dương tạo thành bởi hai điểm trong tập hợp ~n~ điểm đó. Vì các điểm phân biệt, mỗi cặp điểm duy nhất tạo thành đúng một đoạn thẳng. Do đó, bài toán quy về đếm số cách chọn 2 điểm khác nhau từ ~n~ điểm, tức là tính tổ hợp chập 2 của ~n~: C(n,2) = n*(n-1)/2.

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;
    cout << n * (n - 1) / 2;
}

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

Với ~n~ điểm phân biệt, số đoạn thẳng có độ dài dương chính là số cách chọn 2 điểm khác nhau từ ~n~ điểm, công thức là C(n,2) = n*(n-1)/2. Đây là công thức chuẩn, chỉ cần một phép tính, không cần lặp.

Cách Xử lý trường hợp đặc biệt

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

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

Đây là cách tiếp cận cẩn thận hơn khi xét các trường hợp đặc biệt: n=0 hoặc 1 cho ra 0 đoạn, n=2 cho ra 1 đoạn. Tuy nhiên, với công thức C(n,2), các trường hợp này cũng được xử lý đúng (n*(n-1)/2 = 0 khi n=0 hoặc 1, bằng 1 khi n=2).

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

Bài học kinh nghiệm

• Bài toán chỉ yêu cầu đếm số cặp điểm, không cần quan tâm tọa độ hay vị trí.
• Mỗi cặp điểm tạo thành duy nhất một đoạn thẳng, do đó bài toán quy về tính tổ hợp chập 2 của n.

Lỗi thường gặp

• Sử dụng kiểu dữ liệu quá nhỏ (ví dụ int) dẫn đến tràn số khi n lớn (n~10^6, n*(n-1)/2 có thể ~5*10^11, vượt quá giới hạn int).
• Viết sai công thức tính tổ hợp chập 2, ví dụ n*(n-1) mà không chia 2, hoặc chia 2 trước gây mất chính xác (nếu chia 2 trước khi nhân).