Олимпиада по информатике 2025-2026 муниципальный этап Сказ о Луче Великой Справедливости

Администратор

7 месяцев назад

Олимпиада по информатике 2025-2026 муниципальный этап Сказ о Луче Великой Справедливости

olimp-inf-tatmunits-2025-E

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))

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

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))