#P2972. Laser-Ball

    ID: 1982 远端评测题 3000ms 64MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>Northeastern Europe 2004, Western Subregion

Laser-Ball

Description

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

Input

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.

Output

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

Source

Northeastern Europe 2004, Western Subregion