Tác giả:
Reviewer:
Trong phần 1, chúng ta đã tìm hiểu cách sử dụng vector để giải các bài toán hình học. Bây giờ chúng ta sẽ học cách sử dụng một vài kiến thức đại số tuyến tính cơ bản để tìm giao điểm của đường thẳng, sau đó áp dụng để giải quyết một số bài toán khác.
Lưu ý: một số hình ảnh được chụp từ Desmos, và đều có link Desmos tương ứng ở dưới mỗi hình, các bạn có thể nhấn vào link để tương tác với hình và các tham số.
Một trong những bài toán con phổ biến nhất trong các bài toán hình học là giao điểm đường thẳng. Mặc dù phổ biến nhưng nhiều người vẫn gặp rắc rối với nó.
Đầu tiên, ta có câu hỏi nhỏ là: đường thẳng được cho dưới dạng nào? và chúng ta muốn sử dụng ở dạng nào? Ở trường hợp lý tưởng thì đường thẳng sẽ ở dạng $Ax + By = C$, với $A, B, C$ là các hệ số xác định đường thẳng. Tuy nhiên, ta hiếm khi được cho đường thẳng ở dạng này, nhưng ta có thể dễ dàng có được từ hai điểm cho trước. Ví dụ có hai điểm phân biệt $(x_1,y_1)$ và $(x_2,y_2)$, và để tìm $A, B, C$ cho phương trình trên, ta đặt:
Bất kể đường thẳng được cho dưới dạng nào, ta luôn có thể chọn được hai điểm phân biệt thuộc đường thẳng, sau đó tính $A, B, C$.
Tiếp theo, giả sử ta có hai đường thẳng, được cho bởi hai phương trình:
Để tìm giao điểm của hai đường thẳng, ta chỉ cần giải hệ hai phương trình với hai ẩn $x,y$:
double det = A1 * B2 - A2 * B1;
if (det == 0) {
// Lines are parallel or coincident
if (A1 * C2 == A2 * C1) {
// Lines are coincident
}
else {
// Lines are parallel
}
}
else {
double x = (B2 * C1 - B1 * C2) / det;
double y = (A1 * C2 - A2 * C1) / det;
}
Để biết được công thức ở đoạn code trên từ đâu ra, ta nhân phương trình thứ nhất với $B_2$, và nhân phương trình thứ hai với $B_1$:
Kế tiếp, lấy phương trình thứ nhất trừ phương trình thứ hai:
Cuối cùng, chia cả hai vế cho $A_1B_2 - A_2B_1$, ta sẽ có phương trình giải $x$:
Phương trình giải $y$ thu được bằng biến đổi tương tự:
Như vậy ta sẽ có được toạ độ giao điểm của hai đường thẳng, nhưng sẽ thế nào nếu đây là hai đoạn thẳng? Trong trường hợp này, ta cần kiểm tra xem giao điểm tìm được có nằm trên hai đoạn thẳng hay không. Nếu đoạn thẳng nối hai điểm $(x_1, y_1)$ và $(x_2, y_2)$, để kiểm tra xem $(x, y)$ có thuộc đoạn thẳng hay không, ta chỉ cần kiểm tra $min(x_1, x_2) \le x \le max(x_1, x_2)$ và làm tương tự cho $y$.
Ta cũng nên cẩn thận với vấn đề về độ chính xác của số thực. Nếu giao điểm nằm ngay trên đầu mút của đoạn thẳng, hoặc nếu đoạn thẳng nằm ngang hoặc thẳng đứng, một phép so sánh tầm thường có thể có vấn đề. Trong những trường hợp đó, ta có thể thực hiện so sánh với một giá trị sai số nào đó (thường là $10^{-9}$) hoặc sử dụng phân số.
Ngoài ra, ta còn có thể sử dụng tích có hướng để kiểm tra hai đoạn thẳng giao nhau với ưu điểm là không phụ thuộc vào sai số khi tọa độ các đỉnh đều là số nguyên.
Nhắc lại phần 1: Với góc $\alpha$ thỏa mãn $0° < \alpha < 180°$ thì $\sin(\alpha) > 0$ nên nếu góc ngược chiều kim đồng hồ $\theta < 180°$ thì tích có hướng dương, ngược lại tích có hướng âm.
Để biết thứ tự của bộ 3 điểm $A,B,C$, ta tính tích có hướng $\overrightarrow{\rm AB} \times \overrightarrow{\rm AC}$:
Nếu tồn tại 3 trong 4 điểm đầu mút thẳng hàng, ta kiểm tra xem có tồn tại đầu mút của đoạn thẳng này thuộc đoạn thẳng kia hay không:
Nếu không tồn tại 3 trong 4 điểm đầu mút thẳng hàng thì 2 đoạn thẳng $AB$ và $CD$ giao nhau khi:
Để $C$ và $D$ nằm khác phía đối với đường thẳng $AB$ thì:
$\Longrightarrow (\overrightarrow{\rm AB} \times \overrightarrow{\rm AC}) \cdot (\overrightarrow{\rm AB} \times \overrightarrow{\rm AD}) < 0$
Từ đó, ta có hệ sau:
Nhấn vào đây để tương tác với hình trên Desmos.
const double eps = 1e-9;
int sign(double x) {
if (x > eps) return 1;
if (x < -eps) return -1;
return 0;
}
double cross(Vec AB, Vec AC) {
return AB.x * AC.y - AC.x * AB.y;
}
double dot(Vec AB, Vec AC) {
return AB.x * AC.x + AB.y * AC.y;
}
bool intersect(Point A, Point B, Point C, Point D) {
int ABxAC = sign(cross(B - A, C - A));
int ABxAD = sign(cross(B - A, D - A));
int CDxCA = sign(cross(D - C, A - C));
int CDxCB = sign(cross(D - C, B - C));
if (ABxAC == 0 || ABxAD == 0 || CDxCA == 0 || CDxCB == 0) {
// C on segment AB if ABxAC = 0 and CA.CB <= 0
if (ABxAC == 0 && sign(dot(A - C, B - C)) <= 0) return true;
if (ABxAD == 0 && sign(dot(A - D, B - D)) <= 0) return true;
if (CDxCA == 0 && sign(dot(C - A, D - A)) <= 0) return true;
if (CDxCB == 0 && sign(dot(C - B, D - B)) <= 0) return true;
return false;
}
return (ABxAC * ABxAD < 0 && CDxCA * CDxCB < 0);
}
Từ $3$ điểm không thẳng hàng, có duy nhất một đường tròn đi qua $3$ điểm đó. Nhưng làm thế nào để tìm được tâm của nó? Vấn đề này hoá ra là một ứng dụng đơn giản của bài toán giao điểm đường thẳng.
Chúng ta sẽ tìm đường trung trực của 2 đoạn $XY$ và $YZ$, sau đó tìm giao điểm của hai đường này, điểm đó chính là tâm của đường tròn.
Nhấn vào đây để tương tác với hình trên Desmos.
Trong hình học phẳng, đường trung trực của một đoạn thẳng là đường vuông góc với đoạn thẳng tại trung điểm của đoạn thẳng đó.
Các bước để tìm đường trung trực của đoạn $XY$:
Nhấn vào đây để tương tác với hình trên Desmos.
Cho $2$ điểm $X(2,-3)$ và $Y(1,0)$, để tìm đường trung trực của đoạn $XY$, ta thực hiện như sau:
$\Longrightarrow$ phương trình đường thẳng $XY$ có dạng: $3x + y = 3$
Bước 3: Phương trình đường thẳng của đường thẳng vuông góc với đường thẳng $XY$ có dạng: $-x + 3y = D$
Bước 4: Thay tọa độ của trung điểm $M$ vào phương trình $-x + 3y = D$:
Vậy phương trình đường trung trực của đoạn $XY$ là: $-x + 3y = -6$
Làm tương tự cho đoạn $YZ$, chúng ta sẽ có hai phương trình của hai đường trung trực, và có thể tìm giao điểm của chúng như đã đề cập ở trên.
struct Point {
double x, y;
Point() { x = y = 0.0; }
Point(double x, double y) : x(x), y(y) {}
Point operator + (const Point &a) const { return Point(x + a.x, y + a.y); }
Point operator - (const Point &a) const { return Point(x - a.x, y - a.y); }
Point operator * (double k) const { return Point(x * k, y * k); }
Point operator / (double k) const { return Point(x / k, y / k); }
};
struct Line { // Ax + By = C
double a, b, c;
Line(double a = 0, double b = 0, double c = 0) : a(a), b(b), c(c) {}
Line(Point A, Point B) {
a = B.y - A.y;
b = A.x - B.x;
c = a * A.x + b * A.y;
}
};
Line Perpendicular_Bisector(Point A, Point B) {
Point M = (A + B) / 2;
Line d = Line(A, B);
// the equation of a perpendicular line has the form: -Bx + Ay = D
double D = -d.b * M.x + d.a * M.y;
return Line(-d.b, d.a, D);
}
Để lấy đối xứng một điểm $X$ qua một đường thẳng (trục đối xứng), ta tìm giao điểm $Y$ của trục đối xứng và đường thẳng vuông góc với trục đối xứng đi qua $X$, sau đó lấy $X'$ đối xứng với $X$ qua $Y$.
Cho điểm $X(1,-3)$ và đường thẳng $(d):4x-3y=-5$, để tìm điểm $X'$ đối xứng với $X$ qua $(d)$, ta thực hiện như sau:
Bước 1: Gọi đường thẳng đi qua $X$ và vuông góc với trục đối xứng có dạng: $(d'):3x + 4y = D$.
Bước 2: Để tìm $D$, ta chỉ cần thay toạ độ của $X$ vào phương trình:
Nhấn vào đây để tương tác với hình trên Desmos.
struct Line { // Ax + By = C
double a, b, c;
Line(double a = 0, double b = 0, double c = 0) : a(a), b(b), c(c) {}
};
Point intersect(Line d1, Line d2) {
double det = d1.a * d2.b - d2.a * d1.b;
// det != 0 because d1 is perpendicular to d2
return Point((d2.b * d1.c - d1.b * d2.c) / det, (d1.a * d2.c - d2.a * d1.c) / det);
}
Point Symmetry(Point X, Line d) {
// the equation of a perpendicular line has the form: -Bx + Ay = D
double D = -d.b * X.x + d.a * X.y;
Line d2 = Line(-d.b, d.a, D);
Point Y = intersect(d, d2);
Point X2 = Point(2 * Y.x - X.x, 2 * Y.y - X.y);
return X2;
}
Cho điểm $A(x,y)$, để quay điểm $A$ ngược chiều kim đồng hồ một góc $\theta$ quanh gốc tọa độ, ta đơn giản sử dụng công thức:
Lưu ý: vì các ngôn ngữ lập trình sử dụng radian(rad) làm đơn vị chuẩn khi làm việc với các hàm số lượng giác nên ở trong desmos, mình sử dụng đơn vị của số đo góc là radian thay vì độ(°).
Công thức chuyển đổi giữa radian và độ:
Bảng chuyển đổi một số giá trị thường dùng:
Độ | 0° | 15° | 30° | 45° | 60° | 75° | 90° | 180° |
---|---|---|---|---|---|---|---|---|
Radian | 0 | $\frac{\pi}{12}$ | $\frac{\pi}6$ | $\frac{\pi}4$ | $\frac{\pi}3$ | $\frac{5\pi}{12}$ | $\frac{\pi}2$ | $\pi$ |
Nhấn vào đây để tương tác với hình trên Desmos.
Để quay điểm $A$ quanh một điểm $C$ khác không phải gốc tọa độ, ta tịnh tiến hệ tọa độ sao cho $C$ trùng với gốc tọa độ, quay bằng công thức trên rồi tịnh tiến hệ tọa độ về vị trí ban đầu.
Cho $2$ điểm $A(1,4)$ và $C(2,2)$, để quay $A$ ngược chiều kim đồng hồ 1 góc $45°$ quanh $C$, ta thực hiện như sau:
Bước 1: tịnh tiến hệ tọa độ sao cho $C$ trùng với gốc tọa độ. Lúc này, điểm $A$ có tọa độ mới là $A'=(1-2,4-2)=(-1,2)$.
Bước 2: quay $A'$ ngược chiều kim đồng hồ 1 góc $45°$ quanh gốc tọa độ được điểm $B'$:
Vậy quay $A(1,4)$ ngược chiều kim đồng hồ 1 góc $45°$ quanh $C(2,2)$, ta được điểm $B\left( -\dfrac{3\sqrt{2}}{2}+2, \dfrac{\sqrt{2}}{2}+2 \right)$
Nhấn vào đây để tương tác với hình trên Desmos.
Point Rotations(Point A, Point C, double rad) {
Point A2 = A - C;
Point B2 = Point(A2.x * cos(rad) - A2.y * sin(rad), A2.x * sin(rad) + A2.y * cos(rad));
Point B = B2 + C;
return B;
}
Học phải đi đôi với hành, do đó mình đề xuất cho các bạn Codeforces Gym 100168. Tuy đề bài trong gym được viết bằng tiếng Nga nhưng rất ngắn gọn và đi thẳng vào bài toán nên các bạn có thể dễ dàng google translate.
Bên dưới là một số bài tập có liên quan đến bài viết này, mình đã tóm tắt yêu cầu bài toán để các bạn có thể hiểu đề dễ dàng hơn.