Задача E1. Тир (10 баллов)
К задаче добавлено примечание!
Давно были в тире? Мы недавно.
В нашем тире висят и стоят жестяные и алюминиевые банки из под различных напитков. Точнее, висели и стояли.
От наших выстрелов банки мотались из стороны в сторону на верёвке, срывались, звенели, мялись. Это вам не из пальцев стрелять.
Каждая из пуль либо прошла насквозь одной из банок, после чего поражённая банка упала на пол и откатилась в сторону так, что в неё было уже невозможно попасть; либо не попала ни в одну из банок. В любом случае, каждая из пуль застряла в стене, стоящей позади наших банок-мишеней.
Но тот день в прошлом. Осталась только стена с застрявшими в ней пулями и фотография. В попытке восстановить тот день и насладиться им снова мы собрали данные о положении каждой пули в стене, расположении банок и порядке выстрелов.
Помогите определить про каждую пулю, поразила ли она какую-то из банок, и если поразила, то какую именно.
Формат входных данных
В первой строке записаны два целых числа n и m (1≤m,n≤1000) – количество банок, которые были нашей мишенью в тот день, и количество совершённых в тот день выстрелов.
В i-ой из следующих n строк описывается положение i-ой банки. Положение задаётся координатами проекции банки на вертикальную плоскость. Проекция представляет из себя прямоугольник, стороны которого параллельны нанесённой на эту плоскость системы координат. Ось Y этой системы направлена вертикально вверх, а ось X – горизонтально. А прямоугольник задаётся парой точек – своей левой нижней и правой верхней вершинами.
Гарантируется, что ни одна пара этих прямоугольников не имеет ни одной общей точки.
В i-ой из следующих m строк описывается положение i-ой пули в стене. Пули заданы в том же порядке, в котором они выходили из наших дул. Сама стена строго вертикальна, поэтому мы можем считать, что положение задаётся координатами проекции пуль на вертикальную плоскость. Причём траектории движения пуль были строго перпендикулярна этой плоскости. Сами точки задаются парой координат в уже описанной выше системе координат.
Расстояние между банками и стеной по сравнению с расстоянием до стреляющих настолько мало, что мы им пренебрегаем.
Примечание
Значения координат по модулю не превышают 10^9.
Формат выходных данных
В первой и единственной строке выведите m чисел, i-ое из которых говорит, какую из банок i-я пуля прошла насквозь, если такая имеется. Если i не задела ни одну банку, то выведите −1−1, иначе выведите порядковый номер во входных данных банки, которую поразила i-я пуля.
Sample Input:
4 10
0 0 1 1
2 3 3 8
15 15 20 20
10 12 12 13
2 2
0 -1
23 18
13 12
10 13
16 16
17 17
3 5
3 5
3 3
Sample Output:
-1 -1 -1 -1 4 3 -1 2 -1 -1
Ответы
Ответ:
i_n, i_m = input().split()
n = []
m = []
res = ""
n_excluded = []
for n_i in range(int(i_n)):
x1, y1, x2, y2 = input().split()
n.append({
"x1": int(x1), "y1": int(y1),
"x2": int(x2), "y2": int(y2)
})
for m_i in range(int(i_m)):
x, y = input().split()
m.append({
"x": int(x), "y": int(y)
})
for mm in m:
jar_num = 1
collision = False
for nn in n:
if jar_num not in n_excluded and nn['x1'] <= mm['x'] <= nn['x2'] and nn['y1'] <= mm['y'] <= nn['y2']:
collision = True
n_excluded.append(jar_num)
break
jar_num += 1
if collision:
res += " " + str(jar_num)
else:
res += " -1"
print(res)
Объяснение:
Это решение подходит только для E1. В E2 - ошибка Runtime Exception