Hướng giải của Khoảng cách lớn nhất giữa hai điểm

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Cặp điểm xa nhất luôn nằm trên bao lồi. Do đó:

  1. Xây dựng bao lồi bằng thuật toán Monotone Chain.
  2. Sử dụng kỹ thuật Rotating Calipers (thước cặp xoay) để tìm đường kính của bao lồi:

Duy trì hai con trỏ, với mỗi cạnh \((hull[i], hull[i+1])\), tìm điểm \(hull[j]\) xa nhất trên bao lồi bằng cách kiểm tra diện tích tam giác \((hull[i], hull[i+1], hull[j+1])\) có lớn hơn \((hull[i], hull[i+1], hull[j])\) hay không. Khoảng cách lớn nhất được cập nhật qua các cặp \((hull[i], hull[j])\).

Độ phức tạp: \(O(N \log N)\).

Mã nguồn C++

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

struct Point { long long x, y; };

long long cross(const Point& a, const Point& b, const Point& c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

long long dist2(const Point& a, const Point& b) {
    long long dx = a.x - b.x, dy = a.y - b.y;
    return dx * dx + dy * dy;
}

vector<Point> build_hull(vector<Point> p) {
    int n = p.size();
    sort(p.begin(), p.end(), [](const Point& a, const Point& b) {
        return a.x != b.x ? a.x < b.x : a.y < b.y;
    });
    vector<Point> hull;
    for (int i = 0; i < n; i++) {
        while (hull.size() >= 2 && cross(hull[hull.size()-2], hull.back(), p[i]) <= 0)
            hull.pop_back();
        hull.push_back(p[i]);
    }
    int lower = hull.size();
    for (int i = n-2; i >= 0; i--) {
        while (hull.size() > lower && cross(hull[hull.size()-2], hull.back(), p[i]) <= 0)
            hull.pop_back();
        hull.push_back(p[i]);
    }
    hull.pop_back();
    return hull;
}

long long rotating_calipers(const vector<Point>& hull) {
    int m = hull.size();
    if (m <= 2) return m == 2 ? dist2(hull[0], hull[1]) : 0;
    long long ans = 0;
    int j = 1;
    for (int i = 0; i < m; i++) {
        int ni = (i + 1) % m;
        while (true) {
            int nj = (j + 1) % m;
            long long cur = cross(hull[i], hull[ni], hull[j]);
            long long nxt = cross(hull[i], hull[ni], hull[nj]);
            if (nxt > cur) j = nj;
            else break;
        }
        ans = max(ans, dist2(hull[i], hull[j]));
        ans = max(ans, dist2(hull[ni], hull[j]));
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin >> n;
    vector<Point> p(n);
    for (int i = 0; i < n; i++) cin >> p[i].x >> p[i].y;
    vector<Point> hull = build_hull(p);
    cout << rotating_calipers(hull) << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.