Giao Điểm Hai Đoạn Thẳng
Points
18
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề bài
Trên bản đồ quy hoạch giao thông có $T$ cặp tuyến đường thẳng, mỗi tuyến là một đoạn thẳng nối hai điểm trên mặt phẳng tọa độ.
Với mỗi cặp đoạn thẳng $AB$ và $CD$, hãy kiểm tra xem chúng có cắt nhau (có ít nhất một điểm chung, kể cả chạm đầu mút hoặc trùng nhau một phần) hay không.
Dữ liệu vào
- Dòng đầu tiên chứa số nguyên $T$ ($1 \le T \le 10^5$).
- Mỗi bộ test gồm $2$ dòng:
- Dòng 1: $x_A, y_A, x_B, y_B$
- Dòng 2: $x_C, y_C, x_D, y_D$
Dữ liệu ra
- Với mỗi bộ test, in ra
YESnếu hai đoạn thẳng có điểm chung, ngược lại in raNO.
Ví dụ
| Input | Output |
|---|---|
| 4 0 0 4 4 0 4 4 0 0 0 2 0 3 0 5 0 0 0 2 2 2 2 4 0 0 0 4 0 1 1 3 1 |
YES NO YES NO |
Giới hạn
- $1 \le T \le 10^5$
- $|x|, |y| \le 10^9$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion