0013. SplitterGun
| Имя входного файла: | splgun.in |
| Имя выходного файла: | splgun.out |
| Ограничение по времени: | 6 s |
| Ограничение по памяти: | 64 megabytes |
Математику Васе перед экзаменом по геометрии снится страшный сон. Вася стоит на поле брани (плоскости) в точке (x0, y0), и его окружили N кровожадных монстров, расположенных в точках (xi, yi) (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.
Обсудить Отправить решение