Задача . G. Тир

Тир в Берляндском парке культуры и отдыха по праву считается одним из лучших в мире. Ежедневно лучшие стрелки страны оттачивают там свое мастерство, а многочисленные посетители соревнуются в стрельбе по мишеням в борьбе за достойные призы. А недавно директор парка решил сделать онлайн-версию тира. В процессе разработки выяснилось, что нужна программа, эффективно моделирующая процесс стрельбы. Чтобы сформулировать требования к программе, тир был описан формально. Была введена трехмерная декартова система координат, в которой ось X проходила по полу тира по линии, вдоль которой стоят стрелки, ось Y проходила вертикально по стене тира, а положительное направление оси Z совпадало с направлением стрельбы. Плоскость XOY назовем плоскостью стрельбы и будем считать, что все пули выходят из дул в точках этой плоскости и летят параллельно оси Z. Каждая мишень представляет собой прямоугольник, стороны которого параллельны осям X и Y, имеющий положительную z-координату. Все мишени находятся на разном расстоянии от плоскости стрельбы. Пуля попадает в мишень, если она проходит через внутренность или границу соответствующего ей прямоугольника. Когда пуля поражает мишень, мишень падает вертикально вниз, в подпол тира, и больше по ней стрелять нельзя. Мишени достаточно прочные, поэтому пуля не может пробить мишень насквозь, и в случае попадания пуля не летит дальше. На вход программе-симулятору дается расположение всех мишеней, а также координаты всех выстрелов в порядке их появления. Программа должна определить, какая мишень была сбита каждым выстрелом. Если вы еще не догадались, то написать такую программу поручается вам.