Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: 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 (
**X**,_{1}**Y**) – (_{1}**X**,_{2}**Y**), where (_{2}**X**,_{1}**Y**) ≠ (_{1}**X**,_{2}**Y**) and_{2}**X**,_{i}**Y**are real numbers. The height of a mirror is not essential for this problem._{i} - 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(X**_{B}, Y_{B}) - 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**N**≤ 10^{K}^{6}
Input The input contains one data set. A data set starts with a line containing two real numbers Y separated by one or more spaces. The next line contains two integer numbers, _{B}N and K, separated by one or more spaces. The next N lines contain four real numbers X1, _{i}Y1, _{i}X2, _{i}Y2 each, separated by one or more spaces._{i}Output The output contains the word Sample Input
Sample Output
Source Northeastern Europe 2004, Western Subregion |

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

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator