미러리티 리포트

시간 제한2초메모리 제한512 MB

요약

시작점에서 발사한 빨간 공이 각 거울에서 최대 한 번만 튕겨 도착점에 닿는 발사 방향의 수를 구합니다.

난이도: 보통10점 중 7점
유형: 기하, 완전 탐색, 시뮬레이션
정답자: 아직 제출이 없습니다

문제

물리 수업에서 학생은 각자 학기 과제를 완성해야 한다. 여러분은 '붉은 공'이라고 불리는 희귀하고 불안정한 입자의 실험을 골랐다. 붉은 공은 거울에 반사되기 전까지 직선으로 이동한다.

실험 장치는 2차원 평면 위의 직선(길이가 무한할 수도 있다)으로 볼 수 있는 여러 개의 일회 반사 거울로 이루어진다. 일회 반사 거울은 입자가 처음 부딪힐 때에만 입자를 반사하며, 입자가 어느 쪽에서 오든 마찬가지다. 그 뒤로 이 거울은 같은 입자를 항상 통과시킨다.

반사할 때, 입사 경로와 거울의 법선이 이루는 각은 반사 후 출사 경로와 법선이 이루는 각과 같다. 입자가 반사해야 하는 두 거울의 교점에 도달하면 입자는 소멸한다.

선생님이 거울 배치를 만들었다. 주어진 출발 위치에서 발사한 입자가 주어진 도착 위치에 도달하게 하는 발사 방향을 구하라.

입력

첫 줄에 거울의 개수 $N$ ( $0 \le N \le 8$ )이 주어진다. 둘째 줄에는 출발 위치와 도착 위치의 좌표 $S_x$ , $S_y$ , $E_x$ , $E_y$ 가 주어진다. 이어지는 $N$ 개의 줄에는 각 거울의 직선을 정의하는 두 점 $A_x$ , $A_y$ , $B_x$ , $B_y$ 가 주어진다.

모든 좌표는 $-100$ 이상 $100$ 이하의 정수다. 출발 위치와 도착 위치는 서로 다르다. 두 위치는 어느 거울과도 거리가 0이 아니다.

입력은 유효한 해가 입자를 반사할 수 있는 다른 거울과의 교점에서 $10^{-4}$ 보다 가까운 곳에서 반사하도록 요구하지 않는다고 보장된다.

출력

출발 위치에서 발사했을 때 입자가 도착 위치에 도달하게 하는 서로 다른 발사 방향의 개수를 정수 하나로 한 줄에 출력한다.

힌트

그림 1: 입력 예시 1, 2, 3의 도식.

예제3

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