Hiểu bài toán

Bài toán yêu cầu tìm một điểm trong danh sách ~n~ điểm đã cho sao cho tổng khoảng cách Euclid từ điểm đó đến tất cả các điểm còn lại là nhỏ nhất. Nếu có nhiều điểm cùng cho tổng khoảng cách nhỏ nhất, chọn điểm có chỉ số nhỏ nhất (theo thứ tự xuất hiện trong dữ liệu đầu vào). Dữ liệu vào bao gồm số nguyên ~n~ và ~n~ cặp tọa độ ~(x_i, y_i)~. Kết quả cần in ra chỉ số của điểm được chọn và tổng khoảng cách tương ứng làm tròn đến 3 chữ số thập phân.

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

Cách Brute Force (Tối ưu)

#include <bits/stdc++.h>
using namespace std;

struct Point {
    int x, y;
};

double distance(const Point &a, const Point &b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

int main() {
    int n;
    cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].x >> points[i].y;
    }

    double min_sum = 1e18;
    int best_idx = -1;

    for (int i = 0; i < n; i++) {
        double current_sum = 0;
        for (int j = 0; j < n; j++) {
            if (i == j) continue;
            current_sum += distance(points[i], points[j]);
        }
        // So sánh strict (<) để đảm bảo chọn chỉ số nhỏ nhất khi bằng
        if (current_sum < min_sum) {
            min_sum = current_sum;
            best_idx = i + 1; // Chuyển về chỉ số 1-based
        }
    }

    cout << best_idx << " " << fixed << setprecision(3) << min_sum;
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Đây là phương pháp trực tiếp nhất. Với mỗi điểm ~i~ (điểm tâm candidacy), ta tính tổng khoảng cách từ ~i~ đến tất cả các điểm còn lại ~j~ (với ~j \neq i~). Ta duy trì biến lưu tổng khoảng cách nhỏ nhất tìm được và chỉ số điểm tương ứng. Vì ta duyệt theo thứ tự tăng dần của chỉ số, điều kiện current_sum < min_sum (không dùng <=) sẽ đảm bảo rằng nếu gặp một điểm khác có tổng khoảng cách bằng đúng với giá trị nhỏ nhất hiện tại, ta sẽ không cập nhật lại và giữ nguyên chỉ số nhỏ hơn.

Cách Brute Force (Tối ưu)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    int a[n+5], b[n+5];
    for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];

    double res = 1e18;
    // Pass 1: Tìm giá trị nhỏ nhất
    for(int i = 1; i <= n; i++){
        double sum = 0;
        for(int j = 1; j <= n; j++){
            if(j != i){
                sum += sqrt((double)(a[i] - a[j])*(a[i] - a[j]) + (b[i] - b[j])*(b[i] - b[j]));
            }
        }
        res = min(res, sum);
    }

    // Pass 2: Tìm chỉ số đầu tiên khớp với giá trị nhỏ nhất
    for(int i = 1; i <= n; i++){
        double sum = 0;
        for(int j = 1; j <= n; j++){
            if(j != i){
                sum += sqrt((double)(a[i] - a[j])*(a[i] - a[j]) + (b[i] - b[j])*(b[i] - b[j]));
            }
        }
        if(sum == res){
            cout << i << " ";
            break;
        }
    }
    cout << fixed << setprecision(3) << res << endl;
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Cách tiếp cận này thực hiện hai lượt duyệt. Lượt thứ nhất để tìm giá trị tổng khoảng cách nhỏ nhất (res). Lượt thứ hai để tìm chỉ số điểm đầu tiên có tổng khoảng cách bằng res. Cách này cũng đảm bảo chọn được chỉ số nhỏ nhất nhưng tốn thời gian hơn một chút do phải duyệt lại toàn bộ dữ liệu hai lần.

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

Bài học kinh nghiệm

• Vì ~n \leq 100~, độ phức tạp ~O(n^2)~ là hoàn toàn chấp nhận được.
• Công thức tính khoảng cách Euclid giữa hai điểm ~(x_1, y_1)~ và ~(x_2, y_2)~ là ~\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}~.
• Để chọn được chỉ số nhỏ nhất khi có nhiều đáp án, ta chỉ cập nhật biến kết quả khi tìm thấy tổng khoảng cách nhỏ hơn(strictly less) giá trị hiện tại.

Lỗi thường gặp

• Lỗi số thực (Floating Point Error): Khi so sánh hai số thực để kiểm tra sự tương đương (==), có thể xảy ra sai số nhỏ. Tuy nhiên, trong bài toán này, do cách tiếp cận Brute Force tính toán chính xác giá trị cho từng điểm, ta có thể dùng phép so sánh == nếu dữ liệu là số nguyên và cách tính đảm bảo độ chính xác. Tốt hơn hết là dùng phép so sánh khoảng cách (ví dụ: abs(a - b) < 1e-9) nếu lo ngại sai số.
• Sai lệch chỉ số: Các ngôn ngữ lập trình thường bắt đầu đếm chỉ số từ 0 (0-based), trong khi yêu cầu bài toán in ra chỉ số từ 1 (1-based) theo thứ tự danh sách. Cần cộng thêm 1 vào chỉ số trước khi in.