Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
Statistical Charts
Submit Problem
Online Status
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Time Limit: 3000MSMemory Limit: 65536K
Total Submissions: 224Accepted: 50Special 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

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

sample output #1
1 1

sample output #2
1 0

sample output #3


Northeastern Europe 2004, Western Subregion

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator