bzoj#P4431. [Nwerc2015]Hole in One 一杆进洞
[Nwerc2015]Hole in One 一杆进洞
题目描述
珍妮最近去当地的游戏商店买了「一杆进洞」,一个新的迷你高尔夫电脑游戏。正如名称所示,这个游戏的目标是,将球只用一击击进洞里。游戏还借鉴了打砖块风格的游戏元素:在场上,放置了一些墙,它们被球击中就会被摧毁。一个成功的击球的得分取决于破坏墙的数量,所以珍妮不禁要问:在一次「一杆进洞」中能够摧毁的最多的墙数量是多少?
对于这个问题的意向,你可以认为,比赛场地为笛卡尔坐标平面,球的最初位置在原点。墙壁为在该平面中互不相交且与坐标轴平行的线段(即平行于 轴或 轴)。球的直径非常小以至于把它当成一个点。
图1:第一个样例输入的插图:球首先经过 , 号点,并在 号点时穿过了被摧毁的墙。
每当球碰到一堵墙,会发生:
-
球的方向以通常的方式改变:入射角等于反射角。
-
被球触碰的墙被破坏。 游戏逻辑规定,没有墙的废墟存在,认为它消失了。
球的行为也受到击球的力影响。特别的是,最佳的击球可能需要将鼠标放在洞上,然后摧毁一些墙壁,并且只是延迟入洞。
输入格式
一行一个整数 ,墙壁的数量。
一行两个整数 和 ,洞的坐标。
接下来 行,每行各有四个整数 ,, 与 ( 或 ,但不会满足两者),表示墙壁的两个端点。
注意:洞不会在原点也不会在墙上。墙壁不会互相接触或交叉。没有墙会完全在 轴或 轴上。
输出格式
如果没有办法一击入洞,输出「impossible」。否则,输出在一次「一杆进洞」中能够摧毁的最多的墙的数量。
3
4 2
1 1 1 2
2 1 2 2
3 1 3 2
2
1
2 0
1 -1 1 1
impossible
2
-2 4
2 4 2 2
0 6 -2 6
2
数据规模与约定
对于 的数据,,输入的所有的坐标都是整数且绝对值最大 。