Editorial for quaytron: Quay tròn

Hiểu bài toán

Bài toán yêu cầu tìm số lần biến đổi tối thiểu để chuyển một đường tròn ban đầu tâm (s1, s2) bán kính r sang một đường tròn mới tâm (f1, f2) cùng bán kính r. Mỗi lần biến đổi, ta chọn một điểm nằm trên đường tròn hiện tại và xoay toàn bộ đường tròn quanh điểm đó một góc bất kỳ.

Quan sát hình học: Xoay quanh một điểm P trên đường tròn là một phép đẳng hướng (isometry) bảo toàn khoảng cách. Nếu ta xoay đường tròn tâm C1 quanh điểm P, tâm mới C' sẽ nằm trên đường tròn tâm P bán kính PC1. Vì P nằm trên đường tròn cũ, khoảng cách PC1 bằng r. Do đó, từ C1, ta có thể di chuyển tâm đến bất kỳ điểm nào trên đường tròn tâm C1 bán kính r sau 1 bước.

Quy hoạch động/nhị nguyên: Vấn đề trở thành tìm đường đi ngắn nhất từ C1 đến C2 trên mặt phẳng, với mỗi bước di chuyển có độ dài chính xác bằng r (và có thể đổi hướng bất kỳ).

• Nếu khoảng cách d = |C1C2| = 0: Cần 0 bước.
• Nếu d <= 2r: Ta có thể đến đích trong 1 bước (vì đoạn thẳng C1C2 nằm trong bán kính r, nên có thể tìm được điểm P sao cho C2 nằm trên đường tròn tâm P bán kính r).
• Nếu d > 2r: Ta cần nhiều bước. Trong mỗi bước, ta có thể đi một đoạn thẳng dài r. Để đến đích nhanh nhất, ta nên đi theo hướng thẳng đến đích. Số bước tối thiểu là số đoạn r cần thiết để bao phủ quãng đường d. Đây chính là phép chia lấy trần (ceiling) của d/r.

Tuy nhiên, có một trường hợp đặc biệt:

• Nếu d = 2r: Ta cần 1 bước (điểm P nằm ở vị trí trung điểm).
• Nếu d > 2r: Ta cần ceil(d/r) bước.

Tóm lại:

• Nếu d = 0: 0.
• Nếu 0 < d <= 2r: 1.
• Nếu d > 2r: ceil(d / r).

Công thức tổng quát: Nếu d == 0, output 0. Ngược lại, output ceil(d / (2*r)).

Lưu ý quan trọng: Bài toán yêu cầu số nguyên. Ta cần xử lý chính xác giá trị khoảng cách để tránh sai số số học.

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

Cách Phân tích Hình học và Công thức Trực tiếp

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    long long r, s1, s2, f1, f2;
    cin >> r >> s1 >> s2 >> f1 >> f2;

    // Tính bình phương khoảng cách để tránh sai số khi căn bậc 2
    long long dx = s1 - f1;
    long long dy = s2 - f2;
    long long dist_sq = dx*dx + dy*dy;

    if (dist_sq == 0) {
        cout << 0 << endl;
        return 0;
    }

    // Tính khoảng cách thực tế
    double d = sqrt(dist_sq);

    // Công thức: ceil(d / (2*r))
    // Tuy nhiên, cần kiểm tra chia hết hoặc các trường hợp đặc biệt
    // Nếu d <= 2*r, ceil(d / (2*r)) = 1.
    // Nếu d > 2*r, kết quả là số nguyên lớn hơn 1.

    long long res = ceil(d / (2.0 * r));

    cout << res << endl;

    return 0;
}

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

Đây là cách tiếp cận tối ưu và chính xác nhất dựa trên phân tích hình học:

1. Tính khoảng cách d từ tâm cũ đến tâm mới.
2. Nếu d = 0, output 0.
3. Nếu d > 0, số bước cần thiết là số đoạn đường kính 2r cần thiết để che phủ khoảng cách d. Số đoạn này là ceil(d / (2*r)).

Cách này sử dụng hàm sqrt và ceil của thư viện chuẩn. Việc tính bình phương khoảng cách trước (dist_sq) giúp đảm bảo tính chính xác và xử lý trường hợp tọa độ lớn.

Cách Quy hoạch Động/Suy luận Hình học (Kiểm tra chia hết)

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

typedef long long ll;

int main() {
    ll r, s1, s2, f1, f2;
    cin >> r >> s1 >> s2 >> f1 >> f2;

    ll dx = s1 - f1;
    ll dy = s2 - f2;
    ll dist_sq = dx*dx + dy*dy;

    // Tính khoảng cách
    double d = sqrt(dist_sq);

    // Kiểm tra xem d có phải là số nguyên không
    // Nếu d là số nguyên (dấu chấm động) và chia hết cho 2*r
    if (ceil(d) == floor(d) && (ll)d % (2 * r) == 0) {
         cout << (ll)d / (2 * r);
    } else {
         cout << (ll)d / (2 * r) + 1;
    }

    return 0;
}

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

Cách tiếp cận này dựa trên nhận định:

• Nếu khoảng cách d là một bội số của 2r, số bước sẽ chính xác là d / (2r).
• Nếu không, số bước là (d / (2*r)) + 1.

Phương pháp này cố gắng tránh dùng hàm ceil bằng cách kiểm tra chia hết. Tuy nhiên, nó rủi ro hơn do vấn đề dấu phẩy động: (ll)d có thể bị làm tròn sai nếu d rất gần một số nguyên. Ví dụ, nếu d = 2*r - epsilon, (ll)d có thể bằng 2*r - 1 (nếu epsilon nhỏ), dẫn đến kết quả sai. Mặc dù vậy, trong phạm vi dữ liệu của đề bài, nó có thể hoạt động đúng.

Cách Xử lý Sai số Khoảng cách (Kiểu Integer)

#include <iostream>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    long long r, s1, s2, f1, f2;
    cin >> r >> s1 >> s2 >> f1 >> f2;

    long long dx = s1 - f1;
    long long dy = s2 - f2;
    long long dist_sq = dx*dx + dy*dy;
    long long r_sq = (2*r) * (2*r); // (2r)^2

    // Thay vì dùng sqrt, ta có thể dùng phép nhân để so sánh
    // Tuy nhiên, để lấy số bước ta vẫn cần chia cho 2*r
    // Ta có thể làm tròn khoảng cách nếu nó rất nhỏ

    double d = sqrt(dist_sq);

    // Nếu d rất nhỏ (coi như 0)
    if (d < 1e-9) {
        cout << 0 << endl;
        return 0;
    }

    // Tính toán số bước
    long long steps = (long long)ceil(d / (2.0 * r));

    cout << steps << endl;

    return 0;
}

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

Đây là phiên bản cải tiến của Approach 1 để đảm bảo độ chính xác.

• Tính dist_sq bằng số nguyên tuyệt đối để tránh mất mát thông tin.
• Chuyển đổi sang double để tính sqrt.
• Xử lý đặc biệt khoảng cách 0 (d < epsilon).
• Sử dụng ceil để tính số bước.

Đây là phương pháp được khuyến khích sử dụng trong các kỳ thi lập trình khi cần độ chính xác cao.

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

Bài học kinh nghiệm

• Quay quanh một điểm trên đường tròn là phép tịnh tiến tâm theo một vector có độ dài bằng bán kính r.
• Vấn đề trở thành tìm số đoạn thẳng dài r tối thiểu để nối hai điểm tâm.
• Nếu khoảng cách giữa hai tâm là d, số bước cần thiết là ceil(d / (2*r)).

Lỗi thường gặp

• Sai số dấu phẩy động khi tính căn bậc hai hoặc chia số thực, dẫn đến kết quả làm tròn sai (ví dụ: 2.9999999 thay vì 3.0).
• Quên xử lý trường hợp hai tâm trùng nhau (d = 0) nếu công thức chia cho 2*r không xử lý được.
• Sử dụng phép chia lấy phần nguyên (int)(d / (2*r)) thay vì lấy trần (ceiling) khi d không chia hết.