Hole in One#7869
Janine recently went to her local game store and bought "Hole in One", a new mini-golf game for her computer. As indicated by the name, the objective of the game is to shoot a ball into a hole using just one shot. The game also borrows elements from brick breaker style games: in the playing field, several walls are placed that will be destroyed upon being hit by the ball. The score of a successful shot depends on the number of destroyed walls, so Janine wonders: what is the maximum number of walls that can be hit while performing a "Hole in One"?
For the purposes of this problem you can think of the playing field as a cartesian plane with the initial position of the ball at the origin. The walls are non-intersecting axis-parallel line segments in this plane (i.e., parallel to either the axis or the axis). The diameter of the ball is negligible so it is represented as a single point.
Whenever the ball hits a wall, two things happen:
The direction of the ball changes in the usual way: the angle of incidence equals the angle of reflection.
The wall that the ball touched is destroyed. Following common video game logic, no rubble of the wall remains; it will be as though it vanished.
The behavior of the ball is also affected by the power of the shot. In particular, an optimal shot may need to first roll over the hole, then hit some more walls, and only later drop into the hole.
Consists of:
one line with one integer (0 \le n \le 8), the number of walls;
one line with two integers and , the coordinates of the hole;
lines each with four integers x_1, y_1, x_2 and y_2 (either x_1 = x_2, or y_1 = y_2, but not both), representing a wall with end points (x_1, y_1) and (x_2, y_2).
The hole is not at the origin and not on a wall. The walls do not touch or intersect each other. No wall lies completely on the axis or the axis. All coordinates in the input are integers with absolute value at most .
If there is no way to shoot the ball such that it reaches the hole, print "impossible". Otherwise, print the maximum number of walls that can be destroyed in a single "Hole in One" shot.
Example 1
Example 2
Example 3