Hướng dẫn giải của [200 đề thầy Đức] Bài 58: Điểm nằm trong 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.
Hướng dẫn giải
Cho bốn điểm nguyên $A, B, C, D$, kiểm tra điểm $D$ có nằm trong tam giác $ABC$ hoặc trên cạnh, đỉnh của nó hay không. Chỉ cần một phép kiểm tra hình học, các giới hạn nhỏ nên mọi cách làm đều chạy nhanh.
Sub 1: Cộng diện tích — ~O(1)~
Cách nghĩ trực tiếp theo định nghĩa: $D$ nằm trong tam giác $ABC$ khi và chỉ khi tổng diện tích ba tam giác $DAB$, $DBC$, $DCA$ bằng diện tích $ABC$. Dùng diện tích nhân 2 (tích có hướng) để tránh số thực. Đạt 19/19 test.
#include <bits/stdc++.h>
using namespace std;
// Diện tích x 2 của tam giác (P, Q, R) (lấy trị tuyệt đối)
long long area2(long long px, long long py, long long qx, long long qy, long long rx, long long ry) {
return llabs((qx - px) * (ry - py) - (qy - py) * (rx - px));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long xa, ya, xb, yb, xc, yc, xd, yd;
cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd;
// D nằm trong tam giác ABC khi tổng diện tích ba tam giác DAB, DBC, DCA
// đúng bằng diện tích ABC (D nằm trong hoặc trên cạnh).
long long S = area2(xa, ya, xb, yb, xc, yc);
long long S1 = area2(xd, yd, xa, ya, xb, yb);
long long S2 = area2(xd, yd, xb, yb, xc, yc);
long long S3 = area2(xd, yd, xc, yc, xa, ya);
cout << (S == S1 + S2 + S3 ? 1 : 0) << "\n";
return 0;
}
Sub 2: Dấu tích có hướng — ~O(1)~
Tính ba tích có hướng $c1 = (B-A)\times(D-A)$, $c2 = (C-B)\times(D-B)$, $c_3 = (A-C)\times(D-C)$. Điểm $D$ nằm trong hoặc trên cạnh tam giác khi ba số này không có cả số âm lẫn số dương (các số $0$ cho phép, tức $D$ nằm trên cạnh).
Bẫy cần chú ý: giá trị tọa độ đến $10^4$ nên tích có hướng có thể đến khoảng $8 \cdot 10^8$, cần dùng long long cho an toàn.
#include <bits/stdc++.h>
using namespace std;
// Tích có hướng (B - A) x (C - A)
long long cross(long long ax, long long ay, long long bx, long long by, long long cx, long long cy) {
return (bx - ax) * (cy - ay) - (by - ay) * (cx - ax);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long xa, ya, xb, yb, xc, yc, xd, yd;
cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd;
// D nằm cùng phía (hoặc trên) của từng cạnh AB, BC, CA thì nằm trong tam giác.
// Dấu của các tích có hướng phải không cùng âm và không cùng dương.
long long c1 = cross(xa, ya, xb, yb, xd, yd);
long long c2 = cross(xb, yb, xc, yc, xd, yd);
long long c3 = cross(xc, yc, xa, ya, xd, yd);
bool hasNeg = (c1 < 0) || (c2 < 0) || (c3 < 0);
bool hasPos = (c1 > 0) || (c2 > 0) || (c3 > 0);
cout << ((hasNeg && hasPos) ? 0 : 1) << "\n";
return 0;
}
Bình luận