Bài toán yêu cầu bạn xem có tồn tại giao điểm giữa hai đoạn thẳng $AB$ và $CD$ hay không.

Một hướng giải là xác định vị trí tương đối của một bộ 3 điểm trong không gian, từ đó sẽ tìm được cách bố trí của các đoạn thẳng. Có thể giải như sau:

• Như bạn đã biết – Trong không gian 2 chiều, 3 điểm phân biệt có thể thẳng hàng hoặc không, nhưng cũng có thể sắp xếp cùng chiều kim đồng hồ hoặc ngược chiều kim đồng hồ. Khái niệm mở rộng này sẽ là tư tưởng của lời giải.

• Khi bạn xét 3 điểm $P(p_x, p_y)$, $Q(q_x, q_y)$, và $R(r_x, r_y)$ phân biệt, hướng của đường đi gấp khúc $PQR$ có thể được xác định qua công thức:

\begin{equation} s(P, Q, R) = (q_x - p_x)(r_y - q_y) - (q_y - p_y)(r_x - q_x). \end{equation}

• Nếu $s(P, Q, R) = 0$ thì $P$, $Q$ và $R$ thẳng hàng.

• Nếu $s(P, Q, R) > 0$ thì $P$, $Q$ và $R$ tạo thành đường đi ngược chiều kim đồng hồ.

• Nếu $s(P, Q, R) < 0$ thì $P$, $Q$ và $R$ tạo thành đường đi cùng chiều kim đồng hồ.

  (thực chất công thức cũng cho bạn biết vị trí của điểm $R$ so với đường thẳng $PQ$)

• Từ đó bạn rút ra nhận xét:

  • Nếu $A$ và $B$ nằm khác phía đối với đường thẳng $CD$, đồng thời $C$ và $D$ nằm khác phía đối với đường thẳng $AB$ thì hai đoạn $AB$ và $CD$ giao nhau.

  • Hai đoạn $AB$ và $CD$ cũng được coi là giao nhau nếu ít nhất một đầu mút của đoạn này nằm trên đoạn kia.

• Công thức mấu chốt của lời giải một phần có liên quan đến tích vector vô hướng, bạn có thể đọc thêm ở đây.

Code tham khảo:

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define nl '\n'

int state(int px, int py, int qx, int qy, int rx, int ry) {

    int val = (qx - px) * (ry - qy) - (qy - py) * (rx - qx);

    if (val == 0) return 0;
    return (val > 0 ? 1 : 2);
}

bool member(int px, int py, int qx, int qy, int rx, int ry) {

    return min(px, rx) <= qx && qx <= max(px, rx)
        && min(py, ry) <= qy && qy <= max(py, ry);
}

bool cut(int ax, int ay, int bx, int by, int cx, int cy, int dx, int dy) {

    int s1 = state(ax, ay, bx, by, cx, cy);
    int s2 = state(ax, ay, bx, by, dx, dy);
    int s3 = state(cx, cy, dx, dy, ax, ay);
    int s4 = state(cx, cy, dx, dy, bx, by);

    if (s1 != s2 && s3 != s4) return true;

    if (s1 == 0 && member(ax, ay, cx, cy, bx, by)) return true;
    if (s2 == 0 && member(ax, ay, dx, dy, bx, by)) return true;
    if (s3 == 0 && member(cx, cy, ax, ay, dx, dy)) return true;
    if (s4 == 0 && member(cx, cy, bx, by, dx, dy)) return true;

    return false;
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> q;

    bool NL = false;
    while (q--) {

        if (NL) cout << nl;
        int ax, ay, bx, by, cx, cy, dx, dy;

        cin >> ax >> ay;
        cin >> bx >> by;
        cin >> cx >> cy;
        cin >> dx >> dy;

        if (cut(ax, ay, bx, by, cx, cy, dx, dy)) cout << "YES";
        else cout << "NO";

        NL = true;
    }
}