4

Петя нарисовал на клетчатом листке бумаги красивый рисунок прямоугольной формы. Его младшему брату Васе тоже захотелось порисовать, поэтому он вырезал из того же листка бумаги другой прямоугольник. При этом он не делал лишних разрезов, то есть в результате в листке осталась прямоугольная дырка. Кроме того, линии разреза не проходили (даже частично) по границам рисунка Пети. Более того, по границам рисунка не проходили даже продолжения линий разреза.

Ваша задача – по данным о расположении рисунка и прямоугольной дырки определить, испортил ли Вася рисунок старшего брата, другими словами, есть ли на вырезанном Васей прямоугольнике хотя бы маленький фрагмент рисунка Пети.

Вам даны 8 целых чисел — x1, y1, x2, y2, x3, y3, x4, y4, где (x1,y1) - координаты левого нижнего угла рисунка Пети, (x2,y2) - координаты правого верхнего угла рисунка. Аналогично, (x3,y3) — координаты левого нижнего угла вырезанного Васей прямоугольника, (x_4,y_4) — координаты правого верхнего угла вырезанного прямоугольника. Гарантируется, что данные прямоугольники невырождены (x1<x2, y1<y2) и аналогичные неравенства для второго набора координат).

Выведите YES, если Вася испортил рисунок, и NO в противном случае.

Смог написать очень большое решение

x1 = int(input())
y1 = int(input())
x2 = int(input())
y2 = int(input())
x3 = int(input())
y3 = int(input())
x4 = int(input())
y4 = int(input())
x5 = x3
y5 = y4
x6 = x4
y6 = y3

if ((x1 < x3 < x2 and y1 < y3 < y2) or (x1 < x4 < x2 and y1 < y4 < y2) or (x1 < x5 < x2 and y1 < y5 < y2) or (x1 < x6 < x2 and y1 < y6 < y2)):
    print('YES')
elif x3 < x1 and x4 > x2 and (y1 < y3 < y2 or y1 < y4 < y2):
    print("YES")
elif y3 < y1 and y4 > y2 and (x1 < x3 < x2 or x1 < x4 < x2):
    print("YES")
elif x3 < x1 and y3 < y1 and x4 > x2 and y4 > y2:
    print("YES")
else:
    print('NO')

Я проверяю разные варианты расположения рисунка и выреза

Черный - нарисованный, красные - условие входит хотя бы одной точкой в нарисованный, синий - не входит в нарисованный, но все равно портит

Вход: 1 1 2 2 3 3 4 4
Выход: NO
Вход: 1 1 3 3 2 2 4 4
Выход: YES
Вход: 1 1 4 4 2 2 3 3
Выход: YES

Преподаватель говорит о 4-х неравенствах с or/and

Не могу понять как подойти к решению иначе, чтобы убрать лишнее

3 ответа 3

6

Без красивых слов задача формулируется так: на координатной плоскости заданы два прямоугольника со сторонами параллельными осям координат, необходимо проверить пересекаются ли они.

Что же такое на самом деле "прямоугольник на координатной плоскости"? Это множество всех точек удовлетворяющих одновременно двум условиям: (x1 <= x <= x2) && (y1 <= y <= y2). То есть это система из двух неравенств.

Что такое пересечение двух множеств точек? Это система из двух систем:

((x1 <= x <= x2) && (y1 <= y <= y2)) 
&& 
((x3 <= x <= x4) && (y3 <= y <= y4))

Такая система тождественна такой:

((x1 <= x <= x2) && (x3 <= x <= x4)) 
&& 
((y1 <= y <= y2) && (y3 <= y <= y4))

Которая тождественна этой:

(max(x1, x3) <= x <= min(x2, x4)) 
&& 
(max(y1, y3) <= y <= min(y2, y4))

Теперь можно сказать, что прямоугольники пересекаются, если последняя система имеет хотя бы одно решение. И легко заметить, что это решение есть тогда и только тогда, когда

max(x1, x3) <= min(x2, x4)
&&
max(y1, y3) <= min(y2, y4)

Соответственно, программа будет выглядеть следующим образом:

#input
if max(x1, x3) <= min(x2, x4) and max(y1, y3) <= min(y2, y4):
    print('YES')
else:
    print('NO')
4
max(x1,x3) < x2 && min(x2,x4) > x1 && max(y1,y3) < y2 && min(y2,y4) > y1
2

Это вполне можно реализовать одним условием, объединив все if'ы с выводом "YES":

x1 = int(input())
y1 = int(input())
x2 = int(input())
y2 = int(input())
x3 = int(input())
y3 = int(input())
x4 = int(input())
y4 = int(input())
x5 = x3
y5 = y4
x6 = x4
y6 = y3
if ((x1 < x3 < x2 and y1 < y3 < y2) or
(x1 < x4 < x2 and y1 < y4 < y2) or
(x1 < x5 < x2 and y1 < y5 < y2) or
(x1 < x6 < x2 and y1 < y6 < y2) or
(x3 < x1 and x4 > x2 and (y1 < y3 < y2 or y1 < y4 < y2)) or
(y3 < y1 and y4 > y2 and (x1 < x3 < x2 or x1 < x4 < x2)) or
(x3 < x1 and y3 < y1 and x4 > x2 and y4 > y2)):
    print('YES')
else:
    print('NO')

Т.е. каждое условие проверяется оператором or, то есть если хоть одно из решений существует, то значит и ответ должен быть "YES". Если хочешь лучше в этом разобраться, советую почитать про логические операторы в Python.

Что меня еще смутило, так это то, что все значения считываются по одному в каждой строчке, а тесты содержат все данные в одной строчке. Поэтому чтобы решение зашло, нужно сделать так:

x1, y1, x2, y2, x3, y3, x4, y4 = list(map(int, input().split()))
x5 = x3
y5 = y4
x6 = x4
y6 = y3
if ((x1 < x3 < x2 and y1 < y3 < y2) or
(x1 < x4 < x2 and y1 < y4 < y2) or
(x1 < x5 < x2 and y1 < y5 < y2) or
(x1 < x6 < x2 and y1 < y6 < y2) or
(x3 < x1 and x4 > x2 and (y1 < y3 < y2 or y1 < y4 < y2)) or
(y3 < y1 and y4 > y2 and (x1 < x3 < x2 or x1 < x4 < x2)) or
(x3 < x1 and y3 < y1 and x4 > x2 and y4 > y2)):
    print('YES')
else:
    print('NO')

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.