import sys
input_data = sys.stdin.read().strip().split()
if not input_data:
sys.exit(0)
it = iter(input_data)
t = int(next(it))
def check_axis_and_diagonal(rects):
"""
Проверка подзадач 2 и 3:
- горизонтальная прямая (по y)
- вертикальная прямая (по x)
- прямая под 45° (u = x + y)
- прямая под 135° (v = x - y)
"""
# вертикальная: пересечение всех [x1, x2]
max_x1 = max(r[0] for r in rects)
min_x2 = min(r[2] for r in rects)
if max_x1 <= min_x2:
return True
# горизонтальная: пересечение всех [y1, y2]
max_y1 = max(r[1] for r in rects)
min_y2 = min(r[3] for r in rects)
if max_y1 <= min_y2:
return True
# 45 градусов: u = x + y
# Для прямоугольника [x1,x2]×[y1,y2]:
# минимум u в (x1,y1), максимум в (x2,y2)
u_l = -10**30
u_r = 10**30
for x1, y1, x2, y2 in rects:
u_min = x1 + y1
u_max = x2 + y2
if u_min > u_l:
u_l = u_min
if u_max < u_r:
u_r = u_max
if u_l <= u_r:
return True
# 135 градусов: v = x - y
# Для прямоугольника:
# минимум v в (x1,y2), максимум в (x2,y1)
v_l = -10**30
v_r = 10**30
for x1, y1, x2, y2 in rects:
v_min = x1 - y2
v_max = x2 - y1
if v_min > v_l:
v_l = v_min
if v_max < v_r:
v_r = v_max
if v_l <= v_r:
return True
return False
def sign(x):
if x > 0:
return 1
if x < 0:
return -1
return 0
def line_intersects_all(p1, p2, rects):
"""
Проверка: прямая через точки p1, p2 пересекает ли ВСЕ прямоугольники.
rects: список (x1,y1,x2,y2)
"""
x1, y1 = p1
x2, y2 = p2
if x1 == x2 and y1 == y2:
return False # вырожденная прямая
dx = x2 - x1
dy = y2 - y1
for (rx1, ry1, rx2, ry2) in rects:
# четыре угла
corners = (
(rx1, ry1),
(rx1, ry2),
(rx2, ry1),
(rx2, ry2),
)
mn = 0
mx = 0
first = True
for cx, cy in corners:
# ориентация (x1,y1)->(x2,y2) и (x1,y1)->(cx,cy)
# cross = (x2-x1)*(cy-y1) - (y2-y1)*(cx-x1)
cross = dx * (cy - y1) - dy * (cx - x1)
s = sign(cross)
if first:
mn = mx = s
first = False
else:
if s < mn:
mn = s
if s > mx:
mx = s
# если все углы строго по одну сторону (mn>0 или mx<0) — не пересекает
if mn > 0 or mx < 0:
return False
# иначе есть точка на линии или по разные стороны ⇒ пересечение есть
return True
out_lines = []
for _ in range(t):
n = int(next(it))
rects = []
for _j in range(n):
x1 = int(next(it))
y1 = int(next(it))
x2 = int(next(it))
y2 = int(next(it))
rects.append((x1, y1, x2, y2))
# Подзадача 1: n ≤ 2 — всегда Yes
if n <= 2:
out_lines.append("Yes")
continue
# Быстрая проверка осевых и 45/135° прямых (подзадачи 2 и 3)
if check_axis_and_diagonal(rects):
out_lines.append("Yes")
continue
# Подзадача 4: n ≤ 200 — перебор всех направлений по парам углов
# Если n больше — не лезем в куб по времени (на больших тестах всё равно
# нужны более продвинутые выпуклые оболочки, которых здесь нет),
# поэтому остаёмся только с предыдущими проверками.
if n > 200:
out_lines.append("No")
continue
# подготовим углы
corners_per_rect = []
for x1, y1, x2, y2 in rects:
corners_per_rect.append([
(x1, y1),
(x1, y2),
(x2, y1),
(x2, y2),
])
found = False
# перебираем пары различных прямоугольников
for i in range(n):
if found:
break
for j in range(i + 1, n):
# каждую пару углов (один от i, другой от j) – кандидат на прямую
for p1 in corners_per_rect[i]:
if found:
break
for p2 in corners_per_rect[j]:
if p1 == p2:
continue
if line_intersects_all(p1, p2, rects):
found = True
break
# конец по j
out_lines.append("Yes" if found else "No")
sys.stdout.write("\n".join(out_lines))