vi
new
+8
Avatar
Viblo Algorithm @algorithm
10.5K 782 122
Đã đăng vào thg 9 5, 2022 7:28 SA 14 phút đọc
904

Hình học tính toán (phần 2) - Sự giao nhau của các đường thẳng và Tính toán diện tích

Trong bài viết phần 1 về chủ đề Hình học tính toán, chúng ta đã cùng nghiên cứu về cách sử dụng vector trong các bài toán hình học. Còn trong bài viết này, tôi sẽ giới thiệu những vấn đề liên quan tới đường thẳng, giao điểm và sử dụng kiến thức về đại số tuyến tính để tính toán giao điểm, tính toán diện tích, qua đó áp dụng trong những bài toán hình học của lập trình thi đấu.

I. Biểu diễn đường thẳng

Trong Toán học phổ thông, các bạn đã biết có nhiều cách để biểu diễn một đường thẳng, vì thế cũng có nhiều cách biểu diễn đường thẳng trong máy tính, mà tùy vào dữ kiện đề bài ta sẽ chọn cách biểu diễn phù hợp. Dưới đây là một số cách biểu diễn đường thẳng thường dùng trong các bài toán Tin học:

  • Dạng y=ax+by = ax + b: Mỗi đường thẳng được đặc trưng bởi một cặp hệ số aa và b,b, tuy nhiên dạng biểu diễn này không thể hiện được các đường thẳng song song với trục OyOy.
  • Dạng tổng quát: ax+by=cax + by = c. Mỗi đường thẳng có thể được biểu diễn bởi bộ ba hệ số (a,b,c)(a, b, c). Cách làm này gần gũi với đồ thị hàm số, nên nó thường xuyên được sử dụng nhất kể cả trong Toán học hay Tin học. Vector pháp tuyến n⃗(a,b)\vec{n}(a, b) có thể được dùng để viết một phương trình đường thẳng tương đương ngắn gọn hơn: n⃗.OP→=(a,b).(x,y)=ax+by=c\vec{n}.\overrightarrow{OP} = (a, b).(x, y) = ax + by = c với mọi P(x,y)P(x, y) nằm trên đường thẳng. Do đó, dạng tổng quát này còn được kí hiệu là (n⃗,c)(\vec{n}, c).
  • Dạng tham số: (P,d⃗);(P, \vec{d}); trong đó PP là một điểm trên đường thẳng còn d⃗\vec{d} là một vector chỉ phương của đường thẳng với tọa độ là (−b,a)(-b, a). Như vậy, một đường thẳng được xác định bởi bộ bốn số (x0,y0,a,b);(x_0, y_0, a, b); trong đó (x0,y0)(x_0, y_0) là tọa độ điểm PP còn (−b,a)(-b, a) là tọa độ của vector chỉ phương d⃗\vec{d}. Biểu diễn này mang ý nghĩa: Đường thẳng là tập các điểm có tọa độ chính là tọa độ của vector OP→+sd⃗\overrightarrow{OP} + s\vec{d} với mọi S∈RS \in \mathbb{R}.

Khi cần chuyển đổi giữa các biểu diễn, ta thực hiện biến đổi tương đương đại số, kết hợp với công thức chuyển đổi giữa vector chỉ phương d⃗(−b,a)\vec{d}(-b, a) và vector pháp tuyến n⃗(a,b)\vec{n}(a, b).

II. Giao điểm giữa các đường thẳng và ứng dụng

1. Tìm giao điểm của hai đường thẳng

Đây là bài toán phổ biến nhất trong các bài toán về giao điểm, nhưng không phải ai cũng có thể thực hiện thành thạo.

Trong trường hợp lý tưởng, ta sẽ có được hai đường thẳng đều được biểu diễn ở dạng Ax+By=CAx + By = C với A,B,CA, B, C là các hệ số xác định đường thẳng. Tuy nhiên, không phải lúc nào bài toán cũng tuyệt đẹp như vậy. Nhưng may mắn rằng, ta có thể dễ dàng tìm được biểu diễn tổng quát trên dựa vào hai điểm cho trước thuộc đường thẳng. Ví dụ có hai điểm phân biệt (x1,y1)(x_1,y_1) và (x2,y2),(x_2,y_2), và để tìm A,B,CA,B,C cho phương trình trên, ta có công thức:

Đường thẳng dù ở dạng nào, ta cũng có thể chọn được hai điểm phân biệt thuộc đường thẳng và dùng công thức trên để tính A,B,CA, B, C.

Giờ, coi như ta đã thu được hai đường thẳng được cho bởi hai phương trình:

{A1x+B1y=C1 (1)A2x+B2y=C2 (2)\begin{cases}A_1x + B_1y = C_1 \ (1) \\ A_2x + B_2y = C_2 \ (2) \end{cases}

Để tìm giao điểm của hai đường thẳng, ta chỉ cần giải hệ phương trình hai ẩn x,yx, y. Cách làm như sau:

  • Nhân phương trình (1)(1) với B2B_2 và nhân phương trình (2)(2) với B1B_1:

    {A1B2x+B1B2y=B2C1A2B1x+B1B2y=B1C2\begin{cases}A_1B_2x + B_1B_2y = B_2C_1 \\ A_2B_1x + B_1B_2y = B_1C_2 \end{cases}

  • Lấy phương trình thứ nhất trừ hai vế cho phương trình thứ hai, ta được:

    A1B2x+A2B1x=B2C1−B1C2A_1B_2x + A_2B_1x = B_2C_1 - B_1C_2

  • Cuối cùng, chia cả hai vế cho A1B2−A2B1,A_1B_2 - A_2B_1, ta sẽ có phương trình giải ẩn xx:

    x=B2C1−B1C2A1B2−A2B1x = \frac{B_2C_1 - B_1C_2}{A_1B_2 - A_2B_1}

  • Phương trình giải ẩn yy cũng thu được theo cách biến đổi tương tự:

    y=A1C2−A2C1A1B2−A2B1y = \frac{A_1C_2 - A_2C_1}{A_1B_2 - A_2B_1}

Như vậy, ta thu được giao điểm của hai đường thẳng đã cho.

Cài đặt

struct Line
{
    double A, B, C;
};

// Trả về giao điểm hai đường thẳng.
// Riêng hai trường hợp song song hoặc trùng nhau thì ném ngoại lệ.
pair < int, int > find_line_intersection(Line line1, Line line2)
{
    double det = line1.A * line2.B - line2.A * line1.B;
    // Hai đường thẳng song song hoặc trùng nhau.
    if (det == 0)
    {
        if (line1.A * line2.C == line2.A * line1.C)
        {
            throw "Coincident lines";
        }
        else
        {
            throw "Parallel lines";
        }
    }
    else
    {
        double x = line2.B * line1.C - line1.B * line2.C / det;
        double y = line1.A * line2.C - line2.A * line1.C / det;
		
        return {x, y};
    }
}

2. Tìm giao điểm của hai đoạn thẳng

Bài toán tiếp theo là cho bốn điểm A,B,C,DA, B, C, D trên mặt phẳng, cần xác định xem hai đoạn thẳng ABAB và CDCD có giao điểm duy nhất hay không, nếu có thì đưa ra tọa độ của giao điểm đó.

Sử dụng những kiến thức về tích có hướng, ta có thể thực hiện công việc này không mấy khó khăn. Tuy nhiên, trước tiên cần phải xem xét liệu trong số bốn điểm đã cho, có tồn tại ba điểm nào thẳng hàng hay không.

Nhắc lại về hàm CW và CCW

Kiến thức các bạn cần lưu ý ở đây là: Với góc αα thỏa mãn 0°<α<180°0°<α<180° thì sin⁡(α)>0\sin(α)>0 nên nếu góc ngược chiều kim đồng hồ θ<180°θ<180° thì tích có hướng dương, ngược lại tích có hướng âm (đã đề cập ở bài viết trước).

Xét ba điểm A,B,C;A, B, C; Giả sử ta đi từ điểm AA sang điểm BB theo đường thằng và đi tiếp sang điểm CC theo đường thẳng, khi đó:

  • Tích có hướng AB→×BC→\overrightarrow{AB} \times \overrightarrow{BC} sẽ là số dương nếu như chỗ rẽ tại BB là "rẽ trái" (bẻ góc ngược chiều kim đồng hồ). Đây gọi là công thức CCW.
  • Tích có hướng AB→×BC→\overrightarrow{AB} \times \overrightarrow{BC} sẽ là số âm nếu như chỗ rẽ tại BB là "rẽ phải" (bẻ góc ngược thuận kim đồng hồ). Đây gọi là công thức CW.
  • Tích có hướng AB→×BC→\overrightarrow{AB} \times \overrightarrow{BC} sẽ bằng 00 nếu như ba điểm A,B,CA, B, C thẳng hàng.

Kiểm tra giao điểm của hai đoạn thẳng

Trường hợp tồn tại ba điểm thẳng hàng

Nếu tồn tại 33 trong 44 đ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 có thì rõ ràng là 22 đoạn thẳng giao nhau tại ít nhất 11 điểm (tại đầu mút vừa xét):

  • Nếu không thì rõ ràng là 2 đoạn thẳng không thể giao nhau:

Trường hợp không tồn tại ba điểm thẳng hàng

Nếu không tồn tại 33 trong 44 điểm đầu mút thẳng hàng thì 22 đoạn thẳng ABAB và CDCD giao nhau khi:

  • CC và DD nằm khác phía đối với đường thẳng ABAB và
  • AA và BB nằm khác phía đối với đường thẳng CDCD.

Để CC và DD nằm khác phía đối với đường thẳng AB thì:

  • A,B,CA,B,C ngược chiều kim đồng hồ và A,B,DA,B,D cùng chiều kim đồng hồ hoặc
  • A,B,CA,B,C cùng chiều kim đồng hồ và A,B,DA,B,D ngược chiều kim đồng hồ. ⟹(AB→×AC→)⋅(AB→×AD→)<0⟹(\overrightarrow{AB} \times \overrightarrow{AC}) \cdot (\overrightarrow{AB} \times \overrightarrow{AD}) < 0

Từ đó, ta có hệ sau:

Hình minh họa:

Cài đặt

const double eps = 1e-9;

// Xác định dấu của tích có hướng.
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);
}

3. Tìm đường tròn đi qua ba điểm

Ta biết rằng, từ ba điểm không thẳng hàng, luôn luôn tồn tại duy nhất một đường tròn đi qua ba điểm đó. Để tìm được tâm của đường tròn này, ta ứng dụng chính bài toán xác định giao điểm đường thẳng.

Quan sát hình vẽ dưới đây:

Giả sử ba điểm cho trước là X,Y,Z;X, Y, Z; ta sẽ tìm đường trung trực của hai đoạn XYXY và YZ,YZ, sau đó tìm giao điểm của hai đường trung trực này, đó sẽ chính là tâm của đường tròn đi qua ba điểm X,Y,ZX, Y, Z.

Đường trung trực của một đoạn thẳng chính là đường thẳng vuông góc với đoạn thẳng tại trung điểm của nó. Để tìm đường trung trực của đoạn thẳng XY,XY, ta làm như sau:

  • Bước 1: Viết phương trình đường thẳng XY,XY, giả sử nó là Ax+By=CAx + By = C.

  • Bước 2: Tìm trung điểm MM của đoạn XYXY bằng cách lấy trung bình cộng của 22 hoành độ và trung bình cộng của 22 tung độ.

  • Bước 3: Viết phương trình đường thẳng của đường thẳng vuông góc với đường thẳng XYXY có dạng là −Bx+Ay=D−Bx+Ay=D (xem hình vẽ).

  • Bước 4: Thay tọa độ của trung điểm MM vào phương trình đường thẳng ở bước 33 để tìm DD và xác định đường trung trực.

Ví dụ

Với 22 điểm X(2,−3)X(2,−3) và Y(1,0);Y(1,0); để tìm đường trung trực của đoạn XY,XY, ta thực hiện như sau:

  • Bước 1: Viết phương trình đường thẳng XYXY theo đúng công thức:\begin{cases}A = y_Y - y_X = 0 - (-3) = 3 \\ B = x_X - x_Y = 2 - 1 = 1 \\ C = Ax_X + By_X = 3.2 + 1.(-3) = 2 \end{cases}$$ Vậy phương trình đường thẳng $XY$ có dạng: $3x + y = 3$.
  • Bước 2: Đặt MM là trung điểm đoạn thẳng XY,XY, ta có:

    {xM=xX+xY2=2+12=1.5yM=yX+yY2=−3+02=−1.5\begin{cases}x_M = \frac{x_X + x_Y}{2} = \frac{2 + 1}{2} = 1.5 \\ y_M = \frac{y_X + y_Y}{2} = \frac{-3 + 0}{2} = -1.5\end{cases}

  • Bước 3: Phương trình đường thẳng của đường thẳng vuông góc với đường thằng XYXY có dạng: −x+3y=D-x + 3y = D.
  • Bước 4: Thay tọa độ của điểm MM vào phương trình −x+3y=D-x + 3y = D:

    −1.5+3.(−1.5)=D⇔D=−6-1.5 + 3.(-1.5) = D \Leftrightarrow D = -6

Vậy phương trình đường trung trực của đoạn thẳng XYXY là: −x+3y=−6-x + 3y = -6.

Làm tương tự với đoạn thẳng YZ,YZ, 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.

Cài đặt

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); }
};

// Ax + By = C.
struct Line 
{ 
    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);
}

III. Tính toán diện tích

1. Diện tích tam giác

Có khá nhiều công thức giải tích để tính diện tích tam giác, tùy vào dữ kiện đề bài cho mà ta có thể lựa chọn cách tính phù hợp. Dưới đây là một số cách thường dùng:

  • Nếu biết độ dài một cạnh của tam giác là aa và chiều cao tương ứng với cạnh đó là hh thì diện tích tam giác tính bởi công thức:

    S=a+h2S = \frac{a + h}{2}

  • Nếu biết độ dài hai cạnh của tam giác là aa và b,b, đồng thời góc xen giữa hai cạnh đó có số đo là α\alpha thì diện tích tam giác tính bởi công thức:

    S=ab×sin⁡α2S = \frac{ab \times \sin \alpha}{2}

  • Nếu biết độ dài của ba cạnh tam giác lần lượt là a,b,ca, b, c thì diện tích tam giác có thể tính bởi công thức Heron:

    S=p(p−a)(p−b)(p−c)S = \sqrt{p(p - a)(p - b)(p - c)}

    trong đó pp là nửa chu vi của tam giác.
  • Nếu biết hai vector AB→\overrightarrow{AB} và AC→\overrightarrow{AC} thì diện tích tam giác có thể tính bằng công thức tích chéo:S = \left|\frac{\overrightarrow{AB} \times \overrightarrow{AC}}{2}\right|$$ Tuy nhiên, trên máy tính thì ta cần biết trước tọa độ ba điểm $A = (x_A, y_A), B = (x_B, y_B), C = (x_C, y_C)$ để tính tích chéo (tích có hướng); khi đó công thức trên có thể biến đổi như sau:

    S=∣(xB−xA)(yC−yA)−(xC−xA)(yB−yA)2∣S = \left|\frac{(x_B - x_A)(y_C - y_A) - (x_C - x_A)(y_B - y_A)}{2}\right|

Cài đặt

2. Diện tích đa giác

Ta đã biết rằng, đa giác là một đường gấp khúc khép kín. Trong lập trình, một đa giác sẽ được biểu diễn bằng một dãy các đỉnh liên tiếp nhau A1,A2,A3,…,AnA_1, A_2, A_3, \dots, A_n với tọa độ xác định trên hệ tọa độ Descartes.

Khi đó, diện tích đại số (có thể âm hoặc dương) của một đa giác không tự cắt được tính bằng công thức:

S=(x1−x2)(y1+y2)+(x2−x3)(y2+y3)+⋯+(xn−x1)(yn+y1)2S = \frac{(x_1 - x_2)(y_1 + y_2) + (x_2 - x_3)(y_2 + y_3) + \cdots + (x_n - x_1)(y_n + y_1)}{2}

Và diện tích của đa giác sẽ chính bằng giá trị ∣S∣|S|.

Việc xét diện tích đại số của đa giác có thể giúp chúng ta xác định được các đỉnh của đa giác này đang được liệt kê theo chiều nào. Nếu diện tích đại số là số dương (S>0S > 0) thì dãy các đỉnh được liệt kê theo chiều ngược chiều kim đồng hồ (và ngược lại).

Cài đặt

// Tính diện tích đa giác với dãy đỉnh truyền vào bởi một vector kiểu pair.
double polygon_area(vector < pair < double, double > > vertices)
{
    // Thêm đỉnh đầu tiên vào cuối vector để xét tích cuối cùng trên tử số.
    vertices.push_back(vertices[0]);
	
    int n = vertices.size() - 1;
    double area = 0;
    for (int i = 0; i <= n; ++i)
        area += (vertices[i].first - vertices[i + 1].first) 
		 * (vertices[i].second + vertices[i + 1].second);
		 
    return abs(area) / 2.0;
}

IV. Một số công thức biến đổi tọa độ

1. Phép tịnh tiến

Xét một phép tịnh tiến theo vector (a,b)(a, b). Phép tịnh tiến này sẽ biến một điểm O(0,0)O(0, 0) thành điểm O′(a,b),O'(a, b), điểm I(1,0)I(1, 0) sẽ biến thành điểm I′(a+1,b)I'(a + 1, b) và điểm J(0,1)J(0, 1) sẽ biến thành điểm J′(a,b+1)J'(a, b + 1).

Tổng quát, phép tịnh tiến theo vector (a,b)(a, b) sẽ biến điểm (x,y)(x, y) thành điểm (x‾,y‾);(\overline{x}, \overline{y}); trong đó:

{x‾=x+ay‾=y+b\begin{cases}\overline{x} = x + a \\ \overline{y} = y + b \end{cases}

2. Phép quay

Cho trước điểm A(x,y);A(x, y); để quay điểm AA ngược chiều kim đồng hồ một góc α\alpha quanh gốc tọa độ, ta sử dụng công thức:

{x′=xcos⁡α−ysin⁡αy′=ysin⁡α+ycos⁡α\begin{cases}x' = x \cos \alpha - y \sin \alpha \\ y' = y \sin \alpha + y \cos \alpha\end{cases}

Tuy nhiên, cần lưu ý trong các ngôn ngữ lập trình, số đo góc sử dụng trong các hàm lượng giác sẽ là radian (rad) chứ không phải độ, do đó các bạn cần lưu ý công thức chuyển đổi giữa hai đơn vị này:

π rad=180°⇒{rad=độ×π180độ=rad×180π\pi \ rad = 180° \Rightarrow \begin{cases} rad = \frac{\text{độ} \times \pi}{180} \\ \text{độ} = \frac{rad \times 180}{\pi} \end{cases}

Ngoài ra, chúng ta cũng có thể xây dựng công thức quay một điểm AA quanh một điểm CC bất kì khác gốc tọa độ, bằng cách tịnh tiến hệ tọa độ sao cho điểm CC trùng với gốc tọa độ, rồi lại thực hiện phép quay như đã nêu ở trên.

Ví dụ

Cho 22 điểm A(1,4)A(1,4) và C(2,2),C(2,2), để quay AA ngược chiều kim đồng hồ một góc 45°45° quanh C,C, ta thực hiện như sau:

  • Bước 1: Tịnh tiến hệ tọa độ sao cho CC trùng với gốc tọa độ. Lúc này, điểm AA có tọa độ mới là A′=(1−2,4−2)=(−1,2)A′=(1−2,4−2)=(−1,2).
  • Bước 2: Quay A′A′ ngược chiều kim đồng hồ một góc 45°45° quanh gốc tọa độ được điểm B′B′:

    {xB′=−1.cos⁡45°−2.sin⁡45°=−322yB′=−1.sin⁡45°+2.cos⁡45°=22\begin{cases} x_{B'} = -1.\cos 45° - 2.\sin 45° = -\frac{3\sqrt{2}}{2} \\ y_{B'} = -1.\sin 45° + 2.\cos 45° = \frac{\sqrt{2}}{2}\end{cases}

  • Bước 3: tịnh tiến hệ tọa độ về vị trí ban đầu. Điểm B′B′ có tọa độ mới là: B=(−32–2+2,2–2+2)B=(−32–\sqrt{2}+2,2–\sqrt{2}+2).

Vậy quay A(1,4)A(1,4) ngược chiều kim đồng hồ một góc 45°45° quanh C(2,2),C(2,2), ta được điểm B(−32–2+2,2–2+2)B(−32–\sqrt{2}+2,2–\sqrt{2}+2).

Cài đặt

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); }
};

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;
}

3. Phép đối xứng

Để lấy đối xứng một điểm XX qua một đường thẳng (trục đối xứng), ta tìm giao điểm YY 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,X, sau đó lấy X′X′ đối xứng với X qua YY.

Ví dụ

Cho điểm X(1,−3)X(1, -3) và đường thẳng (d):4x−3y=−5;(d): 4x - 3y = -5; để tìm điểm X′X' đối xứng với XX qua (d),(d), ta thực hiện như sau:

  • Bước 1: Gọi đường thẳng đi qua XX và vuông góc với trục đối xứng có dạng (d′):3x+4y=D(d'): 3x + 4y = D.
  • Bước 2: Để tìm D,D, ta thay tọa độ của XX vào phương trình:

    3.1+4.(−3)=D⇔D=−9⇔(d′):3xx+4y=−93.1 + 4.(-3) = D \Leftrightarrow D = -9 \Leftrightarrow (d'): 3xx + 4y = -9

  • Bước 3: Xác định giao điểm YY của hai đường thẳng (d)(d) và (d′)(d'):

    {xY=B2C1−B1C2A1B2−A2B1=4.(−5)−(−3).(−9)4.4−3.(−3)=−4725=−1.88yY=A1C2−A2C1A1B2−A2B1=4.(−9)−3.(−5)4.4−3.(−3)=−2125=−0.84\begin{cases}x_Y = \frac{B_2C_1 - B_1C_2}{A_1B_2 - A_2B_1} = \frac{4.(-5) - (-3).(-9)}{4.4 - 3.(-3)} = \frac{-47}{25} = -1.88 \\ y_Y = \frac{A_1C_2 - A_2C_1}{A_1B_2 - A_2B_1} = \frac{4.(-9) - 3.(-5)}{4.4 - 3.(-3)} = \frac{-21}{25} = -0.84 \end{cases}

  • Bước 4: Xác định X′X' đối xứng với XX qua (d)(d) bằng công thức: X′=2Y−XX' = 2Y - X (bởi vì YY là trung điểm của đoạn nối XX′XX' nên X+X′=2YX + X' = 2Y):

    {xX′=2xY−xX=2.(−1.88)−1=−4.76yX′=2yY−yX=2.(−0.84)−(−3)=1.32\begin{cases}x_{X'} = 2x_Y - x_X = 2.(-1.88) - 1 = -4.76 \\ y_{X'} = 2y_Y - y_X = 2.(-0.84) - (-3) = 1.32\end{cases}

Hình minh họa:

Cài đặt

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); }
};

// Ax + By = C.
struct Line 
{ 
    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;
}

V. Tài liệu tham khảo

©️ Tác giả: Vũ Quế Lâm từ Viblo

maths Competitive Programming Viblo Viblo Algorithm

All rights reserved

Mục lục


Viblo
Hãy đăng ký một tài khoản Viblo để nhận được nhiều bài viết thú vị hơn.
Đăng kí