Hình Học Tính Toán Cơ Bản: Điểm, Vector, Tích Có Hướng và Giao Đoạn Thẳng
Trong thế giới lập trình thi đấu và các kỳ thi Học sinh giỏi Tin học, các bài toán hình học tính toán (Computational Geometry) luôn được xem là "nỗi ác mộng" đối với nhiều thí sinh. Lý do không chỉ nằm ở các định lý toán học phức tạp, mà phần lớn đến từ sai số số thực (floating-point inaccuracy) và các trường hợp suy biến (corner cases): ba điểm thẳng hàng, hai đoạn thẳng chạm đỉnh, hoặc hai đoạn thẳng song song đè lên nhau.
Nếu sử dụng các hàm lượng giác như sin, cos, atan2 hay phép chia số thực double, code của bạn rất dễ bị sai lệch một lượng \(\epsilon \approx 10^{-9}\), dẫn đến kết quả sai (Wrong Answer) oan uổng. Bài viết này sẽ trang bị cho bạn tư duy chuẩn quốc tế: Hình học nguyên vẹn trên tọa độ số nguyên, làm chủ vector, tích có hướng (Cross Product) và thuật toán kiểm tra giao hai đoạn thẳng chính xác \(100\%\) không bao giờ sợ sai số.
Cấu trúc điểm và vector bằng toạ độ số nguyên
Quy tắc vàng số một của lập trình thi đấu: Nếu đề bài cho toạ độ nguyên, hãy duy trì tính toán trên số nguyên 64-bit (long long) càng lâu càng tốt.
Mỗi điểm \(P(x, y)\) trong mặt phẳng hai chiều cũng có thể xem là một vector bán kính \(\vec{P} = (x, y)\) xuất phát từ gốc tọa độ \(O(0, 0)\). Đoạn thẳng nối từ điểm \(A\) đến \(B\) biểu diễn bởi vector:
\[\vec{AB} = B - A = (x_B - x_A, y_B - y_A)\]
Cài đặt chuẩn C++17 và Python 3
Mã nguồn C++17 và Python 3 được thiết kế chuẩn mực, xử lý chính xác các trường hợp thẳng hàng và cắt biên:
#include <iostream>
#include <algorithm>
using namespace std;
// Cấu trúc Điểm và Vector 2D tọa độ nguyên 64-bit chống tràn số
struct Point {
long long x, y;
Point() : x(0), y(0) {}
Point(long long _x, long long _y) : x(_x), y(_y) {}
Point operator-(const Point& other) const {
return Point(x - other.x, y - other.y);
}
};
// Tích có hướng 2D (Cross Product): u.x * v.y - u.y * v.x
// Xác định hướng rẽ CCW từ A qua B đến C
long long cross_product(Point a, Point b, Point c) {
Point ab = b - a;
Point ac = c - a;
return ab.x * ac.y - ab.y * ac.x;
}
int sgn(long long val) {
if (val > 0) return 1;
if (val < 0) return -1;
return 0;
}
// Kiểm tra điểm R có nằm trong hình hộp giới hạn của đoạn PQ không
bool on_segment(Point p, Point q, Point r) {
return min(p.x, q.x) <= r.x && r.x <= max(p.x, q.x) &&
min(p.y, q.y) <= r.y && r.y <= max(p.y, q.y);
}
// Kiểm tra hai đoạn thẳng AB và CD có giao nhau hay không
bool check_intersection(Point a, Point b, Point c, Point d) {
long long cp1 = cross_product(a, b, c);
long long cp2 = cross_product(a, b, d);
long long cp3 = cross_product(c, d, a);
long long cp4 = cross_product(c, d, b);
// Trường hợp 4 điểm cùng nằm trên một đường thẳng
if (cp1 == 0 && cp2 == 0 && cp3 == 0 && cp4 == 0) {
return max(min(a.x, b.x), min(c.x, d.x)) <= min(max(a.x, b.x), max(c.x, d.x)) &&
max(min(a.y, b.y), min(c.y, d.y)) <= min(max(a.y, b.y), max(c.y, d.y));
}
// Trường hợp giao nhau thông thường hoặc chạm đỉnh / nằm trên cạnh
return (sgn(cp1) * sgn(cp2) <= 0) && (sgn(cp3) * sgn(cp4) <= 0);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
if (!(cin >> t)) return 0;
while (t--) {
Point a, b, c, d;
cin >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
if (check_intersection(a, b, c, d)) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
return 0;
}
import sys
def cross_product(ax, ay, bx, by, cx, cy):
# Vector AB: (bx - ax, by - ay)
# Vector AC: (cx - ax, cy - ay)
return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
def sgn(v):
if v > 0:
return 1
elif v < 0:
return -1
return 0
def check_intersection(ax, ay, bx, by, cx, cy, dx, dy):
cp1 = cross_product(ax, ay, bx, by, cx, cy)
cp2 = cross_product(ax, ay, bx, by, dx, dy)
cp3 = cross_product(cx, cy, dx, dy, ax, ay)
cp4 = cross_product(cx, cy, dx, dy, bx, by)
if cp1 == 0 and cp2 == 0 and cp3 == 0 and cp4 == 0:
return (max(min(ax, bx), min(cx, dx)) <= min(max(ax, bx), max(cx, dx)) and
max(min(ay, by), min(cy, dy)) <= min(max(ay, by), max(cy, dy)))
return (sgn(cp1) * sgn(cp2) <= 0) and (sgn(cp3) * sgn(cp4) <= 0)
def main():
input_data = sys.stdin.read().split()
if not input_data:
return
t = int(input_data[0])
idx = 1
results = []
for _ in range(t):
coords = [int(input_data[idx + i]) for i in range(8)]
idx += 8
if check_intersection(*coords):
results.append("YES")
else:
results.append("NO")
sys.stdout.write("\n".join(results) + "\n")
if __name__ == '__main__':
main()
Tích vô hướng Dot Product và góc giữa hai vector
Cho hai vector \(\vec{u} = (x_1, y_1)\) và \(\vec{v} = (x_2, y_2)\). Tích vô hướng (Dot Product) được định nghĩa:
\[\vec{u} \cdot \vec{v} = x_1 x_2 + y_1 y_2 = |\vec{u}| \cdot |\vec{v}| \cdot \cos \theta\]
Trong đó \(\theta\) là góc tạo bởi hai vector. Do độ dài vector luôn không âm (\(|\vec{u}|, |\vec{v}| \ge 0\)), dấu của tích vô hướng phản ánh trực tiếp tính chất của góc \(\theta\):
- \(\vec{u} \cdot \vec{v} \gt 0\): Góc \(\theta\) là góc nhọn (\(\theta \lt 90^\circ\)).
- \(\vec{u} \cdot \vec{v} = 0\): Hai vector vuông góc nhau (\(\theta = 90^\circ\)).
- \(\vec{u} \cdot \vec{v} \lt 0\): Góc \(\theta\) là góc tù (\(\theta \gt 90^\circ\)).
Ứng dụng quan trọng nhất của tích vô hướng bằng số nguyên là kiểm tra xem một điểm có nằm trong hình chiếu vuông góc lên một đoạn thẳng hay không mà không cần tính căn bậc hai.
Chủ đề này nằm trong Buổi 14 - Geometry cơ bản + Convex Hull của Tài năng lập trình. Xem đề cương
Tích có hướng 2D và phép thử hướng rẽ CCW
Trong không gian 3D, tích có hướng sinh ra một vector vuông góc với mặt phẳng. Nhưng trong mặt phẳng 2D (\(z = 0\)), tích có hướng của hai vector \(\vec{u} = (x_1, y_1)\) và \(\vec{v} = (x_2, y_2)\) là một đại lượng vô hướng đại số (định thức của ma trận \(2 \times 2\)):
\[\vec{u} \times \vec{v} = \begin{vmatrix} x_1 & x_2 \\ y_1 & y_2 \end{vmatrix} = x_1 y_2 - x_2 y_1\]
Ý nghĩa hình học của tích có hướng
- Diện tích hình bình hành: Giá trị tuyệt đối \(|\vec{u} \times \vec{v}|\) chính bằng diện tích hình bình hành tạo bởi hai vector \(\vec{u}\) và \(\vec{v}\). Diện tích tam giác tạo bởi hai vector này là \(\frac{1}{2} |\vec{u} \times \vec{v}|\).
- Xác định vị trí tương đối:
- Nếu \(\vec{u} \times \vec{v} \gt 0\): Vector \(\vec{v}\) nằm ở phía bên trái (ngược chiều kim đồng hồ) so với \(\vec{u}\).
- Nếu \(\vec{u} \times \vec{v} \lt 0\): Vector \(\vec{v}\) nằm ở phía bên phải (cùng chiều kim đồng hồ) so với \(\vec{u}\).
- Nếu \(\vec{u} \times \vec{v} = 0\): Hai vector cùng phương (song song hoặc thẳng hàng).
Hàm kiểm tra hướng rẽ CCW của ba điểm
Cho ba điểm theo thứ tự \(A, B, C\). Khi di chuyển từ \(A\) đến \(B\) rồi rẽ sang \(C\), chúng ta đang rẽ trái, rẽ phải hay đi thẳng? Ta xét hai vector \(\vec{AB} = B - A\) và \(\vec{AC} = C - A\):
\[\text{ccw}(A, B, C) = \vec{AB} \times \vec{AC} = (x_B - x_A)(y_C - y_A) - (y_B - y_A)(x_C - x_A)\]
| Giá trị \(\text{ccw}(A, B, C)\) | Hướng rẽ | Tính chất hình học |
|---|---|---|
| \(\gt 0\) | Rẽ trái (Counter-Clockwise) | \(C\) nằm bên trái đường thẳng định hướng \(AB\) |
| \(\lt 0\) | Rẽ phải (Clockwise) | \(C\) nằm bên phải đường thẳng định hướng \(AB\) |
| \(= 0\) | Thẳng hàng (Collinear) | Ba điểm \(A, B, C\) cùng thuộc một đường thẳng |
long long cross_product(Point a, Point b, Point c) {
Point ab = b - a;
Point ac = c - a;
return ab.x * ac.y - ab.y * ac.x;
}
Lưu ý tràn số: Nếu tọa độ các điểm có giá trị tối đa \(10^9\), hiệu tọa độ lên tới \(2 \times 10^9\). Tích của hai hiệu có thể lên tới \(4 \times 10^{18}\), vượt quá giới hạn số nguyên 32-bit (
int). Phép nhân bắt buộc phải được thực hiện bằng kiểu dữ liệu 64-bitlong longtrong C++ hoặc số nguyên lớn tự động trong Python!
Thuật toán kiểm tra giao hai đoạn thẳng
Cho hai đoạn thẳng \(AB\) và \(CD\). Nhiệm vụ là xác định xem chúng có ít nhất một điểm chung hay không.
1. Phân loại các trường hợp giao nhau
Hai đoạn thẳng giao nhau thuộc một trong hai nhóm trường hợp:
- Giao nhau thực sự (Proper Intersection): Điểm giao nằm chặt chẽ bên trong cả hai đoạn thẳng (không phải mút).
- Giao nhau suy biến (Degenerate / Improper Intersection): Một mút của đoạn này nằm trên đoạn kia, hoặc hai đoạn thẳng cùng nằm trên một đường thẳng và có phần đè lên nhau.
2. Điều kiện giao nhau khi bốn điểm không cùng thẳng hàng
Đoạn thẳng \(AB\) cắt đường thẳng \(CD\) khi và chỉ khi hai điểm \(A, B\) nằm về hai phía khác nhau của đường thẳng \(CD\). Tương tự, \(C, D\) phải nằm về hai phía khác nhau của đường thẳng \(AB\):
\[\begin{cases} \text{sgn}(\text{ccw}(A, B, C)) \times \text{sgn}(\text{ccw}(A, B, D)) \le 0 \\ \text{sgn}(\text{ccw}(C, D, A)) \times \text{sgn}(\text{ccw}(C, D, B)) \le 0 \end{cases}\]
Dấu \(\le 0\) cho phép một mút nằm ngay trên đường thẳng kia (chung mút, chữ T). Muốn kiểm tra giao nhau thực sự (điểm giao không phải mút của đoạn nào), thay \(\le 0\) bằng \(\lt 0\) ở cả hai dòng.
3. Xử lý trường hợp 4 điểm cùng thẳng hàng
Khi cả 4 giá trị \(\text{ccw}\) đều bằng 0, tức là \(A, B, C, D\) đều nằm trên cùng một đường thẳng. Lúc này, điều kiện duy nhất để hai đoạn thẳng có điểm chung là hình chiếu của chúng lên trục \(Ox\) giao nhau VÀ hình chiếu lên trục \(Oy\) giao nhau:
\[\begin{cases} \max(\min(x_A, x_B), \min(x_C, x_D)) \le \min(\max(x_A, x_B), \max(x_C, x_D)) \\ \max(\min(y_A, y_B), \min(y_C, y_D)) \le \min(\max(y_A, y_B), \max(y_C, y_D)) \end{cases}\]
Mã nguồn hoàn chỉnh C++17 và Python 3
Dưới đây là bộ code chuẩn kiểm tra giao hai đoạn thẳng với thời gian \(O(1)\) cho mỗi truy vấn, không dùng bất kỳ phép chia hay hàm số thực nào.
C++17
#include <iostream>
#include <algorithm>
using namespace std;
struct Point {
long long x, y;
Point() : x(0), y(0) {}
Point(long long _x, long long _y) : x(_x), y(_y) {}
Point operator-(const Point& other) const {
return Point(x - other.x, y - other.y);
}
};
long long cross_product(Point a, Point b, Point c) {
Point ab = b - a;
Point ac = c - a;
return ab.x * ac.y - ab.y * ac.x;
}
int sgn(long long val) {
if (val > 0) return 1;
if (val < 0) return -1;
return 0;
}
bool check_intersection(Point a, Point b, Point c, Point d) {
long long cp1 = cross_product(a, b, c);
long long cp2 = cross_product(a, b, d);
long long cp3 = cross_product(c, d, a);
long long cp4 = cross_product(c, d, b);
// Trường hợp 4 điểm cùng nằm trên một đường thẳng
if (cp1 == 0 && cp2 == 0 && cp3 == 0 && cp4 == 0) {
return max(min(a.x, b.x), min(c.x, d.x)) <= min(max(a.x, b.x), max(c.x, d.x)) &&
max(min(a.y, b.y), min(c.y, d.y)) <= min(max(a.y, b.y), max(c.y, d.y));
}
// Trường hợp cắt nhau thông thường hoặc tiếp xúc tại mút
return (sgn(cp1) * sgn(cp2) <= 0) && (sgn(cp3) * sgn(cp4) <= 0);
}
Python 3
def cross_product(ax, ay, bx, by, cx, cy):
return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
def sgn(v):
return 1 if v > 0 else (-1 if v < 0 else 0)
def check_intersection(ax, ay, bx, by, cx, cy, dx, dy):
cp1 = cross_product(ax, ay, bx, by, cx, cy)
cp2 = cross_product(ax, ay, bx, by, dx, dy)
cp3 = cross_product(cx, cy, dx, dy, ax, ay)
cp4 = cross_product(cx, cy, dx, dy, bx, by)
if cp1 == 0 and cp2 == 0 and cp3 == 0 and cp4 == 0:
return (max(min(ax, bx), min(cx, dx)) <= min(max(ax, bx), max(cx, dx)) and
max(min(ay, by), min(cy, dy)) <= min(max(ay, by), max(cy, dy)))
return (sgn(cp1) * sgn(cp2) <= 0) and (sgn(cp3) * sgn(cp4) <= 0)
Bẫy thường gặp trong các bài thi hình học
- Dùng phương trình đường thẳng \(y = ax + b\): Nếu đoạn thẳng thẳng đứng (\(x_A = x_B\)), hệ số góc \(a = \frac{y_B - y_A}{x_B - x_A}\) sẽ gây lỗi chia cho 0 (
ZeroDivisionErrorhoặcFloating Point Exception). Phép thử CCW bằng tích có hướng hoàn toàn miễn nhiễm với lỗi này. - Quên kiểm tra cả hai chiều: Điều kiện \(C, D\) nằm về hai phía của đường thẳng \(AB\) là chưa đủ. Nếu chỉ kiểm tra một chiều, hai đoạn thẳng có thể bị nhận nhầm là cắt nhau khi đường thẳng kéo dài của đoạn này cắt đoạn kia nhưng bản thân đoạn này quá ngắn, không chạm tới. Ví dụ \(AB\) từ \((0, 0)\) đến \((1, 1)\) và \(CD\) từ \((3, 0)\) đến \((0, 3)\): \(C, D\) nằm về hai phía của đường thẳng \(AB\), nhưng \(A, B\) cùng phía với đường thẳng \(CD\) nên hai đoạn không cắt nhau. Bắt buộc phải kiểm tra cả \(A, B\) đối với \(CD\).
- Tràn số với tọa độ \(10^9\): Trong C++, phép nhân
(bx - ax) * (cy - ay)nếu hai biến là kiểuintsẽ bị tràn số sinh ra số âm trước khi gán cholong long. Luôn ép kiểu sanglong longhoặc định nghĩa tọa độ làlong longngay từ đầu.
Luyện ngay trên Big-O Coding
Để củng cố kiến thức và kiểm tra trực tiếp độ chính xác của chương trình, bạn hãy thực hành ngay các bài tập sau trên hệ thống Big-O Coding:
Làm thế nào để tìm chính xác tọa độ giao điểm nếu hai đoạn thẳng cắt nhau?
Khi đã khẳng định hai đoạn thẳng cắt nhau và không cùng phương, giao điểm duy nhất \(I\) có thể biểu diễn dưới dạng tỉ số diện tích tam giác: \[I = C + \vec{CD} \cdot \frac{|\text{ccw}(A, B, C)|}{|\text{ccw}(A, B, C)| + |\text{ccw}(A, B, D)|}\] Cách tính này chỉ thực hiện phép chia ở bước cuối cùng, giúp giảm thiểu tối đa sai số làm tròn số thực.
Tích có hướng có tổng quát hóa cho đa giác \(N\) đỉnh được không?
Có! Công thức dây giày (Shoelace formula) tính diện tích đa giác \(N\) đỉnh thực chất là tổng đại số tích có hướng của các cạnh liên tiếp: \[S = \frac{1}{2} \left| \sum_{i=1}^N (x_i y_{i+1} - x_{i+1} y_i) \right|\] với quy ước đỉnh \(N+1\) quay vòng lại đỉnh \(1\).
Khi nào bắt buộc phải dùng số thực trong hình học tính toán?
Số thực chỉ bắt buộc khi đề bài yêu cầu tính khoảng cách Euclid thật (\(\sqrt{\Delta x^2 + \Delta y^2}\)), bán kính đường tròn ngoại tiếp / nội tiếp, hoặc góc lượng giác. Khi đó, hãy sử dụng kiểu double hoặc long double với sai số chấp nhận \(\epsilon = 10^{-9}\) và tránh dùng toán tử so sánh == trực tiếp.
Nguồn tham khảo
- CP-Algorithms - Check if two segments intersect - Hướng dẫn chi tiết thuật toán kiểm tra giao đoạn thẳng.
- VNOI Wiki - Hình học tính toán phần 1: Những khái niệm cơ bản - Điểm, vector, tích vô hướng và tích có hướng; phần 2 bàn về giao nhau của đường thẳng, đoạn thẳng.
- USACO Guide - Geometry Primitives - Tích có hướng, giao đoạn thẳng, diện tích đa giác cho phân hạng Platinum.
Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.


