0013. SplitterGun

Имя входного файла:	splgun.in
Имя выходного файла:	splgun.out
Ограничение по времени:	6 s
Ограничение по памяти:	64 megabytes

Математику Васе перед экзаменом по геометрии снится страшный сон. Вася стоит на поле брани (плоскости) в точке (x₀, y₀), и его окружили N кровожадных монстров, расположенных в точках (x_i, y_i) (i = 1, 2, ..., N). У Васи есть уникальное оружие √ "splittergun". Это оружие стреляет пулей, которая летит параллельно земле с огромной постоянной скоростью, равной 1 у.е. Когда пуля попадает в живого монстра или Васю, ее энергия взрыва преобразуется таким образом, что от точки взрыва разлетаются еще 3 пули, а монстр (или Вася) умирает. Новые пули движутся с той же скоростью, что и взорвавшаяся. Одна из этих пуль продолжает траекторию породившей ее пули, а остальные две движутся перпендикулярно этому направлению, в разные стороны. Можно считать, что взрыв происходит мгновенно. Так как пули летят очень быстро, можно считать, что все монстры и Вася стоят на месте.

Проснувшись, Вася хочет проанализировать свой сон, и узнать, кто из монстров погибнет и в какой момент времени, а также попадет ли пуля в него самого. Если пуля попадает в уже убитого монстра или Васю, то она пролетает прямо. Если две пули одновременно попадают в монстра, то они обе взрываются. Столкновением пуль в полете можно пренебречь. Можно считать, что скорость пули √ одна единица расстояния в единицу времени.

Формат входного файла

В первой строке входного файла три целых числа N, Dx, Dy. N - количество монстров (1 ≤ N ≤ 100000), (Dx, Dy) √ координаты вектора направления Васиного выстрела. В последующих N+1 строках заданы пары чисел √ координаты Васи и монстров. Координаты всех точек по модулю не превосходят 10000.

Формат выходного файла

В выходной файл выведите с точностью до четырех знаков после десятичной точки N+1 вещественных чисел: в первой строке время, когда будет убит Вася, а в следующих N строках время смерти каждого монстра в единицах времени. Выведите -1.0000, если Вася или монстр выжил.

Пример:

splgun.in	splgun.out
1 1 0 0 0 1 0	-1.0000 1.0000
3 1 0 0 0 1 0 1 1 0 1	4.0000 1.0000 2.0000 3.0000

Источник: Командное школьное первенство Республики Карелия по программированию, май 2008.

Обсудить       Отправить решение



Версия для печати