bzoj#P4431. [Nwerc2015]Hole in One 一杆进洞

[Nwerc2015]Hole in One 一杆进洞

题目描述

珍妮最近去当地的游戏商店买了「一杆进洞」,一个新的迷你高尔夫电脑游戏。正如名称所示,这个游戏的目标是,将球只用一击击进洞里。游戏还借鉴了打砖块风格的游戏元素:在场上,放置了一些墙,它们被球击中就会被摧毁。一个成功的击球的得分取决于破坏墙的数量,所以珍妮不禁要问:在一次「一杆进洞」中能够摧毁的最多的墙数量是多少?

对于这个问题的意向,你可以认为,比赛场地为笛卡尔坐标平面,球的最初位置在原点。墙壁为在该平面中互不相交且与坐标轴平行的线段(即平行于 xx 轴或 yy 轴)。球的直径非常小以至于把它当成一个点。

图1:第一个样例输入的插图:球首先经过 1122 号点,并在 33 号点时穿过了被摧毁的墙。

每当球碰到一堵墙,会发生:

  • 球的方向以通常的方式改变:入射角等于反射角。

  • 被球触碰的墙被破坏。 游戏逻辑规定,没有墙的废墟存在,认为它消失了。

球的行为也受到击球的力影响。特别的是,最佳的击球可能需要将鼠标放在洞上,然后摧毁一些墙壁,并且只是延迟入洞。

输入格式

一行一个整数 nn,墙壁的数量。

一行两个整数 xxyy,洞的坐标。

接下来 nn 行,每行各有四个整数 x1x_1y1y_1x2x_2y2y_2x1=x2x_1 = x_2y1=y2y_1 = y_2,但不会满足两者),表示墙壁的两个端点。

注意:洞不会在原点也不会在墙上。墙壁不会互相接触或交叉。没有墙会完全在 xx 轴或 yy 轴上。

输出格式

如果没有办法一击入洞,输出「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

数据规模与约定

对于 100%100 \% 的数据,0n80 \le n \le 8,输入的所有的坐标都是整数且绝对值最大 10001000