Hướng dẫn giải của Vị trí tương đối của điểm và tam giác
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
,
Editorial for ptit030: Vị trí tương đối của điểm và tam giác
Hiểu bài toán
Xác định vị trí tương đối của một điểm D so với một tam giác ABC cho trước. Bài toán yêu cầu in ra 'YES' nếu điểm D nằm hoàn toàn trong tam giác (không nằm trên cạnh), và 'NO' trong các trường hợp còn lại (nằm ngoài hoặc nằm trên cạnh).
Các cách tiếp cận
Cách Phương pháp diện tích (Area Method)
#include <stdio.h>
#include <stdlib.h>
int main() {
long long xa, ya, xb, yb, xc, yc, xd, yd;
scanf("%lld %lld %lld %lld %lld %lld", &xa, &ya, &xb, &yb, &xc, &yc);
scanf("%lld %lld", &xd, &yd);
// Tính diện tích sử dụng công thức diện tích tam giác từ tọa độ (Cross Product)
// Diện tích ABC
double s_abc = abs((xb - xa) * (yc - ya) - (xc - xa) * (yb - ya)) / 2.0;
// Diện tích ABD
double s_abd = abs((xb - xa) * (yd - ya) - (xd - xa) * (yb - ya)) / 2.0;
// Diện tích BCD
double s_bcd = abs((xb - xd) * (yc - yd) - (xc - xd) * (yb - yd)) / 2.0;
// Diện tích CAD (hoặc ACD)
double s_acd = abs((xc - xa) * (yd - ya) - (xd - xa) * (yc - ya)) / 2.0;
// Kiểm tra nếu D nằm trên cạnh (một trong các diện tích con bằng 0)
if (s_abd == 0 || s_bcd == 0 || s_acd == 0) {
printf("NO");
} else {
// Kiểm tra tổng diện tích các tam giác con có bằng diện tích tam giác lớn không
// Sử dụng sai số nhỏ do số thực
if (s_abc - (s_abd + s_bcd + s_acd) < 1e-9) {
printf("YES");
} else {
printf("NO");
}
}
return 0;
}
- Time Complexity: O(1)
- Space Complexity: O(1)
Phương pháp này dựa trên giả thuyết toán học: Điểm D nằm trong tam giác ABC nếu và chỉ nếu diện tích tam giác ABC bằng tổng diện tích của ba tam giác con ABD, BCD và CAD. Nếu D nằm trên cạnh, một trong ba diện tích con sẽ bằng 0. Nếu D nằm ngoài, tổng ba diện tích con sẽ lớn hơn diện tích ABC. Lưu ý: Do tính toán với số thực, cần dùng sai số nhỏ (epsilon) khi so sánh để tránh lỗi làm tròn.
Cách Phương pháp hướng (Barycentric/Vector Cross Product)
#include <stdio.h>
#include <stdlib.h>
int main() {
long long xa, ya, xb, yb, xc, yc, xd, yd;
scanf("%lld %lld %lld %lld %lld %lld", &xa, &ya, &xb, &yb, &xc, &yc);
scanf("%lld %lld", &xd, &yd);
// Tính vectơ hướng (cross product) cho các cạnh so với điểm D
// Công thức: (x2 - x1)*(y3 - y1) - (x3 - x1)*(y2 - y1)
// VD: Tính hướng của DA so với DB
long long cp1 = (xb - xa) * (yd - ya) - (xd - xa) * (yb - ya);
long long cp2 = (xc - xb) * (yd - yb) - (xd - xb) * (yc - yb);
long long cp3 = (xa - xc) * (yd - yc) - (xd - xc) * (ya - yc);
// Kiểm tra nếu điểm nằm trên cạnh (bằng 0)
if (cp1 == 0 || cp2 == 0 || cp3 == 0) {
printf("NO");
}
// Kiểm tra tất cả có cùng dấu (dương hoặc âm)
// Nếu cùng dương hoặc cùng âm thì điểm nằm trong
else if ((cp1 > 0 && cp2 > 0 && cp3 > 0) || (cp1 < 0 && cp2 < 0 && cp3 < 0)) {
printf("YES");
} else {
printf("NO");
}
return 0;
}
- Time Complexity: O(1)
- Space Complexity: O(1)
Phương pháp này dùng đệ quy vectơ (cross product) để xác định hướng tương đối. Ta xét ba cạnh của tam giác ABC. Với mỗi cạnh, ta kiểm tra xem điểm D nằm ở bên trái hay bên phải của cạnh đó. Nếu D nằm cùng một bên (cùng dấu cross product) so với cả ba cạnh của tam giác, D nằm trong tam giác. Nếu D nằm trên bất kỳ cạnh nào (cross product bằng 0), kết quả là 'NO'. Phương pháp này chính xác và không dùng số thực.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(1) | O(1) | Phương pháp diện tích (Area Method) |
| 2 | O(1) | O(1) | Phương pháp hướng (Barycentric/Vector Cross Product) |
Bài học kinh nghiệm
- Tổng diện tích các tam giác con tạo bởi điểm D và các cạnh tam giác bằng diện tích tam giác gốc khi D nằm trong tam giác.
- Vectơ cross product cho biết hướng tương đối của ba điểm. Điểm D nằm trong tam giác nếu nó nằm cùng hướng (cùng bên) so với cả ba cạnh của tam giác.
Lỗi thường gặp
- Lỗi so sánh số thực (double): Cần dùng sai số (epsilon) thay vì so sánh trực tiếp bằng dấu '=='.
- Quên kiểm tra trường hợp điểm nằm trên cạnh: Điểm nằm trên cạnh được coi là 'không nằm trong tam giác', do đó cần kiểm tra giá trị bằng 0 của diện tích hoặc cross product.
- Trộn lẫn thứ tự đỉnh khi tính diện tích/cross product dẫn đến sai dấu.
Bình luận