Các khái niệm cơ bản

Chúng ta sẽ tìm hiểu các kỹ thuật hình học thông qua các cấu trúc dữ liệu và thuật toán đặc biệt.

Kỹ thuật cần thiết

Một số từ vựng chuyên ngành:

• Slope - hệ số góc
• Intersection - giao điểm
• Half-plane intersection - giao các nửa mặt phẳng
• Area - diện tích

Cấu trúc Vector

struct Vector {
	double x, y;
	Vector(double x0 = 0, double y0 = 0) : x(x0), y(y0) {}
	Vector operator +(const Vector& v) const {
		return Vector(x + v.x, y + v.y);
	}
	double cross(const Vector& v) const {
		return x * v.y - y * v.x;
	}
	double length() const {
		return sqrt(x*x + y*y);
	}
	Vector unit() const {
		double len = length();
		return Vector(x/len, y/len);
	}
};

Các hàm tiện ích

double distance(const Vector& a, const Vector& b) {
	return sqrt((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y));
}

Vector intersection(const Vector& A, const Vector& B, 
				   const Vector& C, const Vector& D) {
	double t1 = (C - A).cross(B - A);
	double t2 = (B - A).cross(D - A);
	return Vector((C.x*t2 + D.x*t1)/(t1 + t2),
				 (C.y*t2 + D.y*t1)/(t1 + t2));
}

Bài toán bao lồi

Thuật toán Graham tìm bao lồi:

1. Sắp xếp các điểm theo góc cực
2. Sử dụng stack để kiểm tra tính lồi
3. Phức tạp độ O(n log n)

Mã giả

sort(points, points + n);
stack<Point> s;
s.push(points[0]);
for (int i = 1; i < n; i++) {
	while (s.size() >= 2) {
		Point p1 = s.top();
		s.pop();
		Point p2 = s.top();
		if (ccw(p2, p1, points[i]) > 0) {
			s.push(p1);
			break;
		}
	}
	s.push(points[i]);
}

Phương pháp Rotating Calipers

Tìm đường kính của bao lồi:

• Duyệt từng cạnh của bao lồi
• Tìm điểm đối cực (antipodal point)
• Tính khoảng cách tối đa

Giao các nửa mặt phẳng

Các bước thực hiện:

1. Sắp xếp các đường thẳng theo góc cực
2. Sử dụng deque để duy trì các ràng buộc
3. Loại bỏ các đường thẳng không cần thiết

Bài toán bao tròn tối thiểu

Thuật toán ngẫu nhiên tăng dần:

Circle min_circle(vector<Point> points) {
	random_shuffle(points.begin(), points.end());
	Circle c;
	for (int i=0; i

Tổng Minkowski

Công thức: A ⊕ B = {a + b | a ∈ A, b ∈ B}

Ứng dụng trong kiểm tra va chạm giữa các đa giác lồi

Chuyển đổi đồ thị phẳng thành đồ thị đối ngẫu

Các bước xây dựng:

• Loại bỏ cạnh thừa
• Phân vùng mặt phẳng
• Xây dựng đỉnh và cạnh đối ngẫu

Các lưu ý quan trọng

• Luôn sử dụng epsilon (1e-8) khi so sánh số thực
• Tránh tràn số khi tính tích chéo
• Kiểm tra kỹ điều kiện biên