Khoảng cách giữa hai đoạn thẳng

Xem dạng PDF
Gửi bài giải
Điểm: 0,25 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 64M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho hai đoạn thẳng ~L_1~ và ~L_2~, hãy tìm khoảng cách giữa đoạn thẳng ~L_1~ và đoạn thẳng ~L_2~ đó.

Input

Dòng đầu tiên gồm bốn số nguyên dương ~x_1, y_1, x_2, y_2~ (~-10^9 \le x_1, y_1, x_2, y_2 \le 10^9~) lần lượt là toạ độ của hai điểm đầu mút của đoạn thẳng ~L_1~.

Dòng thứ hai gồm bốn số nguyên dương ~x_3, y_3, x_4, y_4~ (~-10^9 \le x_3, y_3, x_4, y_4 \le 10^9~) lần lượt là toạ độ của hai điểm đầu mút của đoạn thẳng ~L_2~.

Output

Gồm một dòng duy nhất là khoảng cách từ đoạn thẳng ~L_1~ đến đoạn thẳng ~L_2~.

Đáp án được tính là đúng nếu sai số không quá ~10^{-6}~.

Sample Input 1

1 1 2 2
2 1 3 0

Sample Output 1

0.707107

Bình luận

Hãy đọc nội quy trước khi bình luận.


  • 22
    tronglee  đã bình luận lúc 19, Tháng 8, 2024, 3:20

    Để tìm khoảng cách giữa hai đoạn thẳng trên mặt phẳng khi biết tọa độ của các đầu mút, bạn có thể làm theo các bước sau:

    Bước 1: Kiểm tra xem hai đoạn thẳng có giao nhau không.

    • Nếu hai đoạn thẳng giao nhau, thì khoảng cách giữa chúng là 0.

    Để kiểm tra hai đoạn thẳng có giao nhau hay không, bạn có thể sử dụng phương pháp dựa trên tích có hướng (cross product) và nguyên tắc về sự thay đổi hướng (orientation). Dưới đây là cách thực hiện:

    Giả sử bạn có hai đoạn thẳng:

    • Đoạn thứ nhất có các đầu mút A(x1, y1) và B(x2, y2).
    • Đoạn thứ hai có các đầu mút C(x3, y3) và D(x4, y4).

    1: Xác định hướng của ba điểm Hướng của ba điểm P(xp, yp), Q(xq, yq), R(xr, yr) được tính như sau:

    • Tính giá trị val = (yq - yp) * (xr - xq) - (xq - xp) * (yr - yq).
      • Nếu val = 0: Ba điểm thẳng hàng.
      • Nếu val > 0: Ba điểm có hướng ngược chiều kim đồng hồ.
      • Nếu val < 0: Ba điểm có hướng theo chiều kim đồng hồ.

    2: Kiểm tra hướng của các cặp điểm Tính hướng cho các cặp điểm sau:

    • o1 = hướng của A, B, C.
    • o2 = hướng của A, B, D.
    • o3 = hướng của C, D, A.
    • o4 = hướng của C, D, B.

    3: Kiểm tra giao nhau Hai đoạn thẳng AB và CD giao nhau nếu thoả mãn một trong các điều kiện sau:

    1. o1 và o2 khác nhau, o3 và o4 khác nhau.
    2. o1 = 0 và điểm C nằm trên đoạn AB.
    3. o2 = 0 và điểm D nằm trên đoạn AB.
    4. o3 = 0 và điểm A nằm trên đoạn CD.
    5. o4 = 0 và điểm B nằm trên đoạn CD.

    4: Kiểm tra điểm có nằm trên đoạn thẳng không (nếu val = 0)

    • Điểm P nằm trên đoạn QR nếu: min(xq, xr) <= xp <= max(xq, xr) và min(yq, yr) <= yp <= max(yq, yr).

    Bước 2: Nếu không giao nhau, tính khoảng cách giữa các điểm đầu mút của một đoạn đến đoạn kia.

    • Đoạn thẳng thứ nhất có các đầu mút A(x1, y1) và B(x2, y2).
    • Đoạn thẳng thứ hai có các đầu mút C(x3, y3) và (D(x4, y4).

    Khoảng cách từ điểm P(xp, yp) đến đoạn thẳng CD được tính bằng:

    1. Tìm đoạn thẳng vuông góc từ P đến đoạn CD, kiểm tra xem chân đường vuông góc nằm trên đoạn CD không.
    2. Nếu chân đường vuông góc nằm trên đoạn CD, thì khoảng cách chính là khoảng cách từ P đến đường thẳng CD.
    3. Nếu chân đường vuông góc không nằm trên đoạn CD, thì khoảng cách là khoảng cách từ P đến điểm gần nhất trong hai điểm C và D.

    Bước 3: Tính khoảng cách giữa các đoạn thẳng

    • Tính khoảng cách từ A đến đoạn CD.
    • Tính khoảng cách từ B đến đoạn CD.
    • Tính khoảng cách từ C đến đoạn AB.
    • Tính khoảng cách từ D đến đoạn AB.

    Khoảng cách nhỏ nhất trong các khoảng cách này chính là khoảng cách giữa hai đoạn thẳng.

    Bước 4: Kết quả

    • Kết quả cuối cùng là giá trị nhỏ nhất trong các khoảng cách tính ở bước 3.