## 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(px,py), Q(qx,qy), và R(rx,ry) 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:
s(P,Q,R)=(qx−px)(ry−qy)−(qy−py)(rx−qx).
-
- 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:
#∈clude<bitsstdc++.h>usingnamespacestd;#def∈e∫longlong#def∈enl′n′∫state(∫px,∫py,∫qx,∫qy,∫rx,∫ry){∫val=(qx-px)⋅(ry-qy)-(qy-py)⋅(rx-qx);if