Hướng giải của Kiểm tra điểm trong bao lồi

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

Xây dựng bao lồi bằng thuật toán Monotone Chain. Sau đó sử dụng kỹ thuật tìm kiếm nhị phân trên góc để kiểm tra điểm có nằm trong bao lồi với độ phức tạp \(O(\log M)\) mỗi truy vấn.

Các bước kiểm tra:

  1. Lấy điểm đầu tiên \(hull[0]\) làm gốc.
  2. Các điểm còn lại được sắp xếp theo góc từ \(hull[0]\) (do tính chất của bao lồi).
  3. Kiểm tra xem điểm \(p\) có nằm trong góc quét từ \(hull[1]\) đến \(hull[M-1]\) không.
  4. Dùng tìm kiếm nhị phân để xác định \(p\) nằm giữa hai tia \(hull[0] \rightarrow hull[i]\) và \(hull[0] \rightarrow hull[i+1]\).
  5. Kiểm tra tích có hướng \(cross(hull[i], hull[i+1], p) \ge 0\) để xác định \(p\) có nằm trong tam giác \((hull[0], hull[i], hull[i+1])\) hay không.

Độ phức tạp: \(O(N \log N + Q \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);
}

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;
}

bool inside(const vector<Point>& hull, const Point& p) {
    int m = hull.size();
    if (m < 3) return false;
    if (cross(hull[0], hull[1], p) < 0) return false;
    if (cross(hull[0], hull[m-1], p) > 0) return false;
    int lo = 1, hi = m - 1;
    while (hi - lo > 1) {
        int mid = (lo + hi) / 2;
        if (cross(hull[0], hull[mid], p) >= 0) lo = mid;
        else hi = mid;
    }
    return cross(hull[lo], hull[hi], p) >= 0;
}

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);
    int q; cin >> q;
    while (q--) {
        Point pt; cin >> pt.x >> pt.y;
        cout << (inside(hull, pt) ? "CO\n" : "KHONG\n");
    }
    return 0;
}

Nhận xét

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