Hiểu bài toán

Bài toán yêu cầu tính tổng quãng đường đi nhỏ nhất của Spider-Man (A) và LV (B) để bán kẹo cho N nhóm học sinh. Các ràng buộc quan trọng:

1. Cả A và B đều xuất phát từ vị trí bắt đầu (xa, ya) và (xb, yb).
2. Khi bán kẹo, họ phải đi theo quy trình: Vị trí hiện tại -> Nhóm học sinh -> Túi kẹo (xc, yc) để lấy thêm kẹo -> Quay lại vị trí ban đầu. Tuy nhiên, do cả hai cùng bán và có thể mang theo kẹo sẵn từ đầu, bài toán có thể được chuyển đổi: Chi phí cơ bản cho mỗi nhóm học sinh là 2 * distance(nhóm, túi kẹo) (đi từ túi đến nhóm và trở về). Tuy nhiên, vì cả hai đều có sẵn kẹo ở vị trí xuất phát, họ có thể bán ngay cho một nhóm mà không cần quay về túi ngay.

Phân tích chi tiết:

• Chi phí cơ sở (Base Cost): Nếu không có ai bán sẵn, mỗi nhóm tốn 2 * dist(nhóm, túi).
• Chi phí thay thế:
  • Spider-Man bán cho nhóm i: Thay vì đi túi -> i -> túi (2 * dist(i, c)), A sẽ đi A -> i -> túi (dist(A, i) + dist(i, c)). Tiết kiệm được: 2 * dist(i, c) - (dist(A, i) + dist(i, c)) = dist(i, c) - dist(A, i).
  • Tương tự cho B: Tiết kiệm dist(i, c) - dist(B, i).
• Bài toán trở thành: Chọn một số nhóm cho A, một số nhóm cho B sao cho mỗi nhóm chỉ được giao cho một người (hoặc không ai cả), và tổng tiết kiệm là lớn nhất (tổng đường đi nhỏ nhất).
• Vì A và B chỉ có thể bán tối đa 1 lần (hoặc hiểu theo nghĩa họ chỉ có 1 gói kẹo đầu tiên, sau đó phải về túi), ta cần xét các trường hợp:
  1. Chỉ A bán 1 nhóm, B không bán thêm (hoặc ngược lại).
  2. A và B mỗi người bán 1 nhóm khác nhau.
  3. Một người bán 2 nhóm (nếu dịch vụ cho phép "bán 2 lần" nhưng code mẫu gợi ý chỉ cần tối ưu 1-2 lần).

Dựa trên các giải pháp mẫu, logic tối ưu là:

• Tính tổng chi phí cơ sở: total = 2 * sum(dist(i, c)).
• Tính giá trị tiết kiệm (gain) cho mỗi nhóm nếu A hoặc B bán: gainA[i] = dist(i, c) - dist(A, i), gainB[i] = dist(i, c) - dist(B, i).
• Sắp xếp các nhóm theo gain giảm dần.
• Tìm cách chọn 1 hoặc 2 nhóm (khác nhau) sao cho tổng gain là lớn nhất.

Lưu ý: Trong các test case, số lượng nhóm N lên đến 10^5, yêu cầu thuật toán O(N log N).

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

Cách Greedy Optimization (Tối ưu hóa Tham lam)

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

typedef long double ld;
typedef pair<ld, int> pii;

int ax, ay, bx, by, tx, ty, n;
vector<int> x, y;
vector<pii> gainA, gainB;

ld dist(int x1, int y1, int x2, int y2) {
    return sqrtl(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> ax >> ay >> bx >> by >> tx >> ty >> n;
    x.resize(n); y.resize(n);
    ld total = 0;
    gainA.resize(n); gainB.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        ld dToT = dist(x[i], y[i], tx, ty);
        total += 2.0 * dToT;

        ld dA = dist(x[i], y[i], ax, ay);
        gainA[i] = {dToT - dA, i};

        ld dB = dist(x[i], y[i], bx, by);
        gainB[i] = {dToT - dB, i};
    }

    sort(gainA.rbegin(), gainA.rend());
    sort(gainB.rbegin(), gainB.rend());

    ld ans = total;

    // Case 1: Only A sells one group (or only B)
    ans = min(ans, total - gainA[0].first);
    ans = min(ans, total - gainB[0].first);

    // Case 2: Both A and B sell one group each
    if (n > 1) {
        // If they sell to the same best group, take second best of one
        if (gainA[0].second != gainB[0].second) {
            ans = min(ans, total - gainA[0].first - gainB[0].first);
        } else {
            ans = min(ans, total - gainA[0].first - gainB[1].first);
            ans = min(ans, total - gainA[1].first - gainB[0].first);
        }
    }

    cout << fixed << setprecision(5) << ans << endl;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Thuật toán này dựa trên việc tính toán lợi ích (gain) khi thay vì đi từ túi kẹo, Spider-Man hoặc LV đi từ vị trí ban đầu của họ để bán cho một nhóm học sinh.

1. Tính tổng chi phí cơ sở total nếu không có ai bán sẵn (mỗi nhóm tốn 2*dist(đến túi)).
2. Với mỗi nhóm, tính gainA và gainB là số distance tiết kiệm được nếu A hoặc B bán.
3. Sắp xếp các gain giảm dần.
4. Xét các trường hợp:
   • Một người bán 1 nhóm tốt nhất: total - gain_max.
   • Hai người bán 2 nhóm tốt nhất (nếu khác nhau): total - gainA_max - gainB_max. Nếu trùng nhóm, thử kết hợp (Amax + Bsecond) hoặc (Asecond + Bmax).
5. Kết quả là tổng chi phí cơ sở trừ đi tổng gain lớn nhất tìm được.

Cách Dynamic Programming / Brute Force (N <= 1000)

// Pseudo-code for N <= 1000 approach
// Not efficient for N=10^5 but works for smaller constraints
#include <bits/stdc++.h>
using namespace std;

// ... (khai báo biến)
// double dp[N]; // hoặc dùng map
// Loop qua từng nhóm, thử giao cho A, B hoặc không giao
// Tuy nhiên, do bài toán yêu cầu O(N log N), approach này chỉ để tham khảo
// Logic tương tự tham lam nhưng duyệt kĩ hơn

int main() {
    // ... input ...
    // Base cost: 2 * sum(dist(i, c))
    // Try all combinations of assigning groups to A and B
    // Since A and B only act once effectively, we just need max gain.
    // This is essentially the Greedy approach but can be implemented with loops.
}

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

Đối với các test nhỏ (N <= 1000), ta có thể sử dụng phương pháp duyệt để tìm tổng gain lớn nhất. Tuy nhiên, do ràng buộc N <= 10^5, phương pháp này không khả thi. Các giải pháp mẫu đều chuyển sang phương pháp tham lam O(N log N).

Cách Direct Optimization with Sorting

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>

using namespace std;

typedef long double ld;

struct Point {
    ld x, y;
};

ld dist(Point p1, Point p2) {
    return sqrtl(pow(p1.x - p2.x, 2) + pow(p1.y - p2.y, 2));
}

int main() {
    Point A, B, T;
    int N;
    if (!(cin >> A.x >> A.y >> B.x >> B.y >> T.x >> T.y >> N)) return 0;

    vector<Point> students(N);
    for (int i = 0; i < N; ++i) cin >> students[i].x >> students[i].y;

    ld base_cost = 0;
    vector<pair<ld, int>> diffA(N), diffB(N);

    for (int i = 0; i < N; ++i) {
        ld dT = dist(students[i], T);
        base_cost += 2 * dT;
        diffA[i] = {dT - dist(students[i], A), i};
        diffB[i] = {dT - dist(students[i], B), i};
    }

    sort(diffA.rbegin(), diffA.rend());
    sort(diffB.rbegin(), diffB.rend());

    ld ans = base_cost;

    // Case 0: No one sells (base cost is already set)

    // Case 1: Only A sells
    ans = min(ans, base_cost - diffA[0].first);

    // Case 2: Only B sells
    ans = min(ans, base_cost - diffB[0].first);

    // Case 3: Both sell
    if (N > 1) {
        if (diffA[0].second != diffB[0].second) {
            ans = min(ans, base_cost - diffA[0].first - diffB[0].first);
        } else {
            // Conflict on the best student group
            ans = min(ans, base_cost - diffA[0].first - diffB[1].first);
            ans = min(ans, base_cost - diffA[1].first - diffB[0].first);
        }
    }

    cout << fixed << setprecision(5) << ans << endl;
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Đây là phiên bản chi tiết và tối ưu hóa của Greedy approach.

• Bước 1: Tính chi phí cơ sở là tổng khoảng cách 2 chiều từ túi kẹo đến tất cả học sinh.
• Bước 2: Tính hiệu số (difference) giữa việc đi từ túi so với đi từ A (và B) cho từng học sinh. Hiệu số này chính là lượng đường đi được tiết kiệm.
• Bước 3: Sắp xếp các hiệu số này giảm dần.
• Bước 4: Xử lý các trường hợp đặc biệt khi chỉ số hiệu số lớn nhất của A và B bị trùng (cùng một nhóm học sinh). Nếu trùng, ta phải chọn phương án thay thế là lấy hiệu số lớn nhất của A và hiệu số lớn thứ 2 của B, hoặc ngược lại.
• Đây là cách tiếp cận chuẩn và hiệu quả nhất cho bài toán này.

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

Bài học kinh nghiệm

• Chuyển đổi bài toán từ việc tìm đường đi tối thiểu thành bài toán tối đa hóa sự tiết kiệm (gain) so với chi phí cơ sở (2*dist(T, Student)).
• Vì Spider-Man và LV chỉ có thể bán 1 lần (hoặc chỉ cần tối ưu 1-2 lần bán đầu tiên để đạt tối ưu toàn cục), ta chỉ cần tìm 1 hoặc 2 giá trị gain lớn nhất.
• Xử lý xung đột (conflict) khi cả hai đều muốn bán cho cùng một nhóm học sinh bằng cách so sánh tổng gain của việc nhường lại một bên cho nhóm tiếp theo.

Lỗi thường gặp

• Sử dụng biến float thay vì double hoặc long double dẫn đến sai số精度 (precision error) khi tính căn bậc hai và cộng dồn.
• Quên kiểm tra trường hợp N=1 (không thể chia cho cả A và B nếu họ cùng muốn nhóm đó, hoặc chỉ cần một người bán).
• Lỗi logic khi cho rằng cả A và B có thể bán nhiều hơn 1 nhóm mà không cần quay lại túi. Dựa trên mô tả và code mẫu, mỗi người chỉ bán tối ưu 1 lần (hoặc chỉ xét 2 người bán 1 lần).