## 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](https://wiki.vnoi.info/algo/geometry/basic-geometry-2).
### 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;
}
}
```
noice
Created at
1 likes