当前你的浏览器版本过低,网站已在兼容模式下运行,兼容模式仅提供最小功能支持,网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器:

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

2972:Laser-Ball

Special Judge 特殊评判
题目描述

Mr. X and his friends are great funs of Laser-Ball Game. Basically, the main idea of the game is very simple. Each player of the game has a laser gun and it is necessary to hit an opponent with a laser beam. To make the game more interesting, Mr. X with friends created their own Laser-Ball playground. They rented an empty rectangular hall and set up a number of big mirrors. What makes the game more interesting is the additional ability to shoot into a mirror since that a reflected laser beam also can hit an opponent.

You need to write a program which determines if it is possible to hit an opponent standing in a point B from point A. If such a hit is possible the program needs to give a direction.

To clarify the problem the following rules are given.

  • There are N mirrors in the hall.
  • Each mirror is a rectangle. It is standing vertically on one of its edges. Therefore, a mirror can be described by a pair of coordinates (X1, Y1) – (X2, Y2), where (X1, Y1) ≠ (X2, Y2) and Xi, Yi are real numbers. The height of a mirror is not essential for this problem.
  • Mirrors neither touch nor cross each other.
  • Both sides of a mirror have a reflection layer. A mirror reflects a laser beam according to physical laws. Let’s assume that an edge reflects in the same way as the inner part of a mirror.
  • Let’s assume that a mirror is absolutely thin. Thus, a laser beam can pass parallel to the mirror as close as necessary, even at 0 distance (see example 2 below)
  • A laser beam hits an opponent if it passes the opponent not farther then 10−4
  • A laser beam goes out of point A(0, 0)
  • A opponent is in the point B(XB, YB)
  • A direction of a shoot, which your program needs to calculate, is a vector in a form (dx, dy)
  • When a laser beam hits a mirror it loses some part of its energy. After the beam hit mirrors (K+1) times it can’t hit an opponent. Any mirror can be hit more than once.
  • 0 ≤ N ≤ 100, 1 ≤ K ≤ 10, but NK ≤ 106
输入解释

The input contains one data set. A data set starts with a line containing two real numbers XB and YB separated by one or more spaces. The next line contains two integer numbers, N and K, separated by one or more spaces. The next N lines contain four real numbers X1i, Y1i, X2i, Y2i each, separated by one or more spaces.

输出解释

The output contains the word “impossible”, if the shoot is impossible. Otherwise it contains two real numbers a, b, (separated by one space), which give a direction of the shoot.

输入样例
sample input #1
4.0 0.0
2 1
2 -1 2 1
1 2 3 2

sample input #2
4 0
1 1
1 0 3 0

sample input #3
4 0
1 1
2 -1 2 1
输出样例
sample output #1
1 1

sample output #2
1 0

sample output #3
impossible

该题目是Virtual Judge题目,来自 北京大学POJ

源链接: POJ-2972

最后修改于 2020-10-29T06:48:47+00:00 由爬虫自动更新

共提交 0

通过率 --%
时间上限 内存上限
3000 65536