cpp-205Bước 1Cơ bản
Tính Khoảng Cách Euclid Giữa Hai Điểm 2D
Hình học tính toán và đồ họa máy tính sử dụng khoảng cách Euclid như thước đo cơ bản để tính độ dài đoạn thẳng, phát hiện va chạm và đo độ tương đồng không gian. Việc thực hiện chí…
CHUYÊN ĐỀ C++ THỰC CHIẾN
Bài tập Hình học tính toán (Computational Geometry) trong C++
Mô hình hóa và xử lý các bài toán điểm, đường thẳng, góc và đa giác trong không gian 2D với độ chính xác số học cao, tránh sai số dấu phẩy động.
12
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
1
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
1
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
10
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Lộ trình thực hành đề xuất
Bước 1
Cấu trúc Điểm & Vector
Xây dựng struct Point { double x, y; } và các phép toán cộng trừ vector.
Bước 2
Tích có hướng (Cross Product)
Xác định hướng quay (ngược chiều/thuận chiều kim đồng hồ) và diện tích tam giác.
Bước 3
Giao điểm & Đa giác
Kiểm tra hai đoạn thẳng cắt nhau và tính diện tích đa giác bằng công thức Shoelace.
Bước 4
Bao lồi (Convex Hull)
Cài đặt thuật toán Andrew/Monotone Chain tìm tập bao lồi trong O(N log N).
Lỗi thường gặp & Cách phòng tránh
•
So sánh hai số thực bằng == thay vì dùng hằng số epsilon (abs(a - b) < EPS).
•
Sai số tràn kiểu số nguyên khi tính tích có hướng của tọa độ lớn (cần ép kiểu sang long long hoặc __int128).
Danh sách bài tập thực hành (12 bài)
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Cơ bản 1 bài
Trung bình 1 bài
cpp-193Bước 1Trung bình
Diện tích phần giao của hai hình tròn
Cho hai hình tròn C1(x1, y1, r1) và C2(x2, y2, r2) trên mặt phẳng Oxy.
Nâng cao 10 bài
Thử thách
Thuật toán chuyên sâu: quy hoạch động, đồ thị, cây.
cpp-064Bước 1Nâng cao
Diện tích đa giác và Định lý Pick trên lưới nguyên
Cho một đa giác đơn gồm N đỉnh có tọa độ nguyên. Hãy tính:
cpp-192Bước 2Nâng cao
Giao các nửa mặt phẳng trong O(N log N)
Một nửa mặt phẳng có hướng được biểu diễn bởi tia đi từ điểm P đến điểm Q, quy ước nửa mặt phẳng hợp lệ nằm ở phía bên trái của vector PQ (tức là PQ × PX…
cpp-063Bước 3Nâng cao
Cặp điểm gần nhất: Thuật toán Chia để trị O(N log N)
Cho N điểm trên mặt phẳng 2D. Hãy tìm bình phương khoảng cách Euclid nhỏ nhất giữa hai điểm bất kỳ trong tập điểm.
cpp-062Bước 4Nâng cao
Kiểm tra điểm trong đa giác: Thuật toán Bắn tia Ray Casting
Cho một đa giác gồm N đỉnh V1, V2, …, VN theo thứ tự duyệt viền. Bạn cần trả lời M truy vấn, mỗi truy vấn cho một điểm P(X, Y) và yêu cầu xác định P nằm INSIDE, BOUNDARY hay…
cpp-194Bước 5Nâng cao
Kiểm tra điểm nằm trong đa giác bất kỳ (Winding Number / Ray Casting)
Cho một đa giác đơn (không tự cắt, không nhất thiết lồi) gồm N đỉnh P0, P1, …, PN-1.
Chuyên sâu
Cấu trúc dữ liệu nâng cao và nhiều bước chứng minh.
cpp-113Bước 6Nâng cao
Các Lớp Bao Lồi - Thuật Toán Tách Lớp Vỏ Hành (Onion Peeling)
Cho tập hợp N điểm phân biệt trên mặt phẳng tọa độ Oxy. Quá trình tách lớp vỏ hành (Convex Layers) diễn ra như sau:
cpp-061Bước 7Nâng cao
Bao lồi tập điểm: Thuật toán Chuỗi đơn điệu Andrew Monotone Chain
Cho N điểm trên mặt phẳng 2D. Hãy tìm tập các đỉnh của bao lồi đa giác chứa toàn bộ N điểm này. Nếu có nhiều điểm thẳng hàng trên cạnh của bao lồi, chỉ giữ lại các điểm ở hai đầu m…
cpp-191Bước 8Nâng cao
Tổng Minkowski của hai đa giác lồi trong O(N + M)
Cho hai đa giác lồi P (gồm N đỉnh) và Q (gồm M đỉnh) trên mặt phẳng Oxy. Các đỉnh của mỗi đa giác được liệt kê theo chiều ngược chiều kim đồng hồ (CCW).
cpp-114Bước 9Nâng cao
Định Vị Điểm Trong Phân Hoạch Phẳng Bằng Phân Tách Dải (Slab Decomposition)
Cho một tập hợp các đoạn thẳng không cắt nhau (chỉ có thể tiếp xúc tại mút) chia mặt phẳng thành các miền. Ta xét bài toán đơn giản hóa chuẩn: Cho N đoạn thẳng nằm ngang hoặc xiên…
cpp-112Bước 10Nâng cao
Bao Lồi 3D - Tính Diện Tích Bề Mặt
Cho tập hợp N điểm trong không gian 3 chiều R3. Hãy tính diện tích bề mặt (surface area) của bao lồi 3D tạo bởi N điểm này.