Hướng dẫn giải của Độ đo cô-sin

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, hohoanghai5042011, sussyboy, lephuochauhungvuong

Editorial for radian: Độ đo cô-sin

Hiểu bài toán

Cho n điểm Ai(xi, yi) trên mặt phẳng, không có điểm nào trùng với gốc tọa độ O(0,0). Tìm cặp điểm (Ai, Aj) sao cho góc ∠Ai O A_j là nhỏ nhất. In ra giá trị cô-sin của góc đó.

Góc giữa hai vectơ OAi và OAj có số đo nằm trong khoảng [0, π]. Cô-sin là hàm đơn điệu giảm trên khoảng [0, π], nghĩa là góc càng nhỏ thì cô-sin càng lớn. Do đó, bài toán tìm góc nhỏ nhất tương đương với tìm cặp điểm có cô-sin lớn nhất.

Điểm mấu chốt là góc giữa hai vectori OAi và OAj là góc kề của chúng tại gốc tọa độ. Khi ta sắp xếp các điểm theo góc của vectơ OA_i so với trục hoành (từ -π đến π), thì cặp điểm tạo ra góc kề nhỏ nhất (tại gốc tọa độ) chắc chắn nằm trong danh sách các cặp điểm kề nhau trong danh sách đã sắp xếp (bao gồm cả cặp điểm đầu và cuối danh sách).

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

Cách Brute Force (Lặp kép)

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

using namespace std;

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

    double max_cos = -1.0; // Cosine lon nhat (goc nho nhat)

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            double dot = x[i] * x[j] + y[i] * y[j];
            double len_i = sqrt(x[i] * x[i] + y[i] * y[i]);
            double len_j = sqrt(x[j] * x[j] + y[j] * y[j]);
            double cos_val = dot / (len_i * len_j);
            if (cos_val > max_cos) {
                max_cos = cos_val;
            }
        }
    }

    cout << fixed << setprecision(4) << max_cos << endl;
    return 0;
}

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

Cách tiếp cận này kiểm tra tất cả các cặp điểm (i, j) khác nhau. Với mỗi cặp, tính toán cô-sin bằng công thức tích vô hướng chia cho tích độ dài. Cách này đúng nhưng quá chậm do độ phức tạp O(n^2), không thể chạy được với n lên tới 10^5.

Cách Sắp xếp góc (Sorting Angles)

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

using namespace std;

struct Point {
    double x, y;
    double angle;
};

bool compareAngles(const Point &a, const Point &b) {
    return a.angle < b.angle;
}

int main() {
    int n;
    cin >> n;
    vector<Point> points(n);

    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
        // Tính góc sử dụng atan2, trả về giá trị trong [-pi, pi]
        points[i].angle = atan2(points[i].y, points[i].x);
    }

    // Sắp xếp các điểm theo góc tăng dần
    sort(points.begin(), points.end(), compareAngles);

    double max_cos = -1.0;

    // Kiểm tra tất cả các cặp điểm kề nhau trong danh sách đã sắp xếp
    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n; // Duyệt kề nhau, cặp cuối kiểm tra với cặp đầu

        double dot = points[i].x * points[j].x + points[i].y * points[j].y;
        double len_i = sqrt(points[i].x * points[i].x + points[i].y * points[i].y);
        double len_j = sqrt(points[j].x * points[j].x + points[j].y * points[j].y);
        double cos_val = dot / (len_i * len_j);

        if (cos_val > max_cos) {
            max_cos = cos_val;
        }
    }

    cout << fixed << setprecision(4) << max_cos << endl;
    return 0;
}

Time Complexity: O(n log n)
Space Complexity: O(n)

Đọc dữ liệu và tính góc của mỗi vectơ OA_i so với trục hoành bằng hàm atan2(y, x). Hàm này trả về giá trị từ -π đến π.
Sắp xếp các điểm theo góc tăng dần.
Sau khi sắp xếp, góc kề nhỏ nhất tại gốc tọa độ chỉ có thể nằm giữa hai điểm kề nhau trong danh sách đã sắp xếp. Ta duyệt qua tất cả các cặp kề nhau (kể cả cặp điểm cuối và điểm đầu) và tính cô-sin.
Cô-sin lớn nhất tìm được chính là đáp án. Lưu ý: Cô-sin giảm dần theo góc, nên góc nhỏ nhất tương đương cô-sin lớn nhất.

Cách Tối ưu Vector (Vector Optimization)

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    vector<pair<double, pair<long long, long long>>> points(n);

    for (int i = 0; i < n; ++i) {
        long long x, y;
        cin >> x >> y;
        // Chuyển đổi tọa độ về góc chuẩn [0, 2*PI) để dễ sắp xếp
        double angle = atan2((double)y, (double)x);
        if (angle < 0) angle += 2 * M_PI;
        points[i] = {angle, {x, y}};
    }

    sort(points.begin(), points.end());

    double max_cos = -1.0;

    for (int i = 0; i < n; ++i) {
        int j = (i + 1) % n;
        // Trích xuất tọa độ
        long long x1 = points[i].second.first;
        long long y1 = points[i].second.second;
        long long x2 = points[j].second.first;
        long long y2 = points[j].second.second;

        // Tính toán sử dụng số nguyên để giảm thiểu lỗi số thực (tùy chọn)
        double dot = (double)x1 * x2 + (double)y1 * y2;
        double len1 = sqrt((double)x1 * x1 + (double)y1 * y1);
        double len2 = sqrt((double)x2 * x2 + (double)y2 * y2);

        double cos_val = dot / (len1 * len2);

        if (cos_val > max_cos) {
            max_cos = cos_val;
        }
    }

    cout << fixed << setprecision(4) << max_cos << endl;
    return 0;
}

Time Complexity: O(n log n)
Space Complexity: O(n)

Đây là phiên bản tối ưu hóa của phương pháp sắp xếp góc. Thay vì tính góc atan2 và lưu trữ dưới dạng double, ta có thể chỉ cần sắp xếp theo góc. Tuy nhiên, độ chính xác của atan2 là đủ.

Phương pháp này cũng dựa trên ý tưởng rằng góc kề nhỏ nhất nằm giữa các điểm kề nhau sau khi sắp xếp.

Một tối ưu hóa khác (không có trong code mẫu nhưng có thể áp dụng): Thay vì tính cô-sin trực tiếp (có phép chia và khai căn), ta có thể tối ưu hóa việc so sánh góc. Tuy nhiên, do yêu cầu đầu ra là giá trị cô-sin, việc tính toán trực tiếp là cần thiết.

Code trên là cách tiếp cận chuẩn: Sắp xếp -> Duyệt kề nhau -> Tính cos.

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

Cách tiếp cận	Time	Space	Tên
1	O(n^2)	O(n)	Brute Force (Lặp kép)
2	O(n log n)	O(n)	Sắp xếp góc (Sorting Angles)
3	O(n log n)	O(n)	Tối ưu Vector (Vector Optimization)

Bài học kinh nghiệm

Vấn đề tìm góc nhỏ nhất (0 đến Pi) tương đương với tìm cô-sin lớn nhất.
Khi các điểm được sắp xếp theo góc, góc kề tại gốc tọa độ giữa hai vectơ OAi và OAj chỉ có thể nhỏ nhất nếu Ai và Aj là các điểm kề nhau trong danh sách đã sắp xếp (hoặc cặp điểm đầu và cuối).
Hàm atan2(y, x) là công cụ chính để chuyển đổi tọa độ Cartesian sang góc.

Lỗi thường gặp

Xử lý sai trường hợp góc nằm trên biên (ví dụ: điểm nằm ở góc 359 độ và 1 độ, nếu không xử lý vòng tròn góc, ta có thể nhầm tưởng góc lớn là 358 độ). Sử dụng công thức min(d, first_angle + 2*PI - last_angle) hoặc chia modulo trong vòng lặp là cách xử lý đúng.
Lỗi chính xác số thực khi tính acos hoặc so sánh các số rất gần nhau.
Quên kiểm tra trường hợp các điểm nằm trên cùng một đường thẳng với gốc tọa độ nhưng ngược chiều (góc = Pi).

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.