영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
There are two line segments: the first goes through the points (x_1,y_1) and (x_2,y_2), and the second goes through the points (x_3,y_3) and (x_4,y_4).
Your task is to determine if the line segments intersect, i.e., they have at least one common point.
Input
The first input line has an integer t: the number of tests.
After this, there are t lines that describe the tests. Each line has eight integers x_1, y_1, x_2, y_2, x_3, y_3, x_4 and y_4.
Output
For each test, print "YES" if the line segments intersect and "NO" otherwise.
Constraints
- 1 ≤ t ≤ 10^5
- -10^9 ≤ x_1, y_1, x_2, y_2, x_3, y_3, x_4, y_4 ≤ 10^9
- (x_1,y_1) ≠ (x_2,y_2)
- (x_3,y_3) ≠ (x_4,y_4)
예제
예제 1
5 1 1 5 3 1 2 4 3 1 1 5 3 1 1 4 3 1 1 5 3 2 3 4 1 1 1 5 3 2 4 4 1 1 1 5 3 3 2 7 4
NO YES YES YES YES