홀인원

시간 제한5초메모리 제한256 MB

요약

원점에서 쏜 공이 축에 평행한 벽에 반사되면서 구멍에 들어갈 때 파괴할 수 있는 벽의 최대 개수를 구합니다.

난이도: 어려움10점 중 8점
유형: 백트래킹, 기하, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

자닌은 동네 게임 가게에서 새로 나온 미니 골프 게임 "홀인원"을 샀다. 이름 그대로 단 한 번의 샷으로 공을 홀에 넣는 것이 목표다. 이 게임은 벽돌 깨기의 요소도 가져왔다. 경기장에는 벽이 여러 개 놓여 있고, 공에 맞은 벽은 부서진다. 성공한 샷의 점수는 부순 벽의 개수로 정해지므로, 자닌은 홀인원을 성공시키면서 최대 몇 개의 벽을 맞힐 수 있는지 알고 싶다.

경기장은 좌표평면이고 공의 처음 위치는 원점이다. 벽은 $x$ 축 또는 $y$ 축에 평행한 선분이고 서로 교차하지 않는다. 공의 지름은 무시할 만큼 작아서 하나의 점으로 본다.

그림: 첫 번째 예제 입력을 그린 것이다. 공은 점 1과 점 2에서 벽에 맞고 튕긴다. 점 3을 지날 때 그 자리의 벽은 이미 사라진 뒤다.

공이 벽에 맞으면 두 가지 일이 일어난다.

공의 방향이 바뀐다. 입사각과 반사각은 같다.
맞은 벽이 부서진다. 게임에서 흔히 그렇듯 잔해는 남지 않고, 벽이 있던 자리는 완전히 비게 된다.

벽 선분은 양 끝점을 포함한다. 공이 벽의 끝점에 정확히 닿아도 그 벽은 부서지고 공은 같은 규칙으로 반사된다.

샷의 세기도 자닌이 정한다. 세기에 따라 공이 굴러가는 거리가 달라지며, 공은 홀 위를 여러 번 지나갈 수 있고 그중 원하는 순간에 홀에 빠진다. 그래서 가장 좋은 샷은 홀 위를 먼저 지나간 다음 벽을 더 맞히고 나중에야 홀에 빠지는 경로일 수도 있다.

입력

첫째 줄에 벽의 개수 $n$ ( $0 \le n \le 8$ )이 주어진다.

둘째 줄에 홀의 좌표 $x$ 와 $y$ 가 주어진다.

다음 $n$ 개 줄에 각각 네 정수 $x_1$ , $y_1$ , $x_2$ , $y_2$ 가 주어진다. 끝점이 $(x_1, y_1)$ 과 $(x_2, y_2)$ 인 벽을 뜻하고, $x_1 = x_2$ 와 $y_1 = y_2$ 중 정확히 하나만 성립한다.

홀은 원점에 있지 않고 벽 위에도 있지 않다. 두 벽이 서로 닿거나 교차하는 일은 없다. $x$ 축이나 $y$ 축에 완전히 놓인 벽도 없다. 입력의 모든 좌표는 절댓값이 $1000$ 이하인 정수이다.

출력

공을 홀에 넣는 방법이 없으면 impossible을 출력한다. 넣을 수 있으면 홀인원 한 번으로 부술 수 있는 벽 개수의 최댓값을 출력한다.

예제3

예제 1
입력
```
3
4 2
1 1 1 2
2 1 2 2
3 1 3 2
```
예상 출력
```
2
```
예제 2
입력
```
1
2 0
1 -1 1 1
```
예상 출력
```
impossible
```
예제 3
입력
```
2
-2 4
2 4 2 2
0 6 -2 6
```
예상 출력
```
2
```