Giao Điểm Hai Đoạn Thẳng

Buổi 61 — Hình học tính toán
Points
18
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Submissions
Đề 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 YES nếu hai đoạn thẳng có điểm chung, ngược lại in ra NO.
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
Draft saved