홀인원

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

요약

N개의 선분 장애물과 네 벽 중 하나에 최대 한 번 튕겨 공이 홀에 들어갈 수 있는지 판정한다.

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

문제

미니골프는 출발 위치에 놓인 공을 쳐서 홀에 넣는 경기다. 가는 길에 물체에 튕겨도 된다.

연습을 더 하려고 컴퓨터 프로그램을 만든다. 이 프로그램은 한 번의 샷으로 공을 홀에 넣을 수 있는지 판정한다. 아직 초보라서 홀에 들어가기 전에 최대 한 번만 튕기는 샷만 친다.

코스는 직사각형이고 그 안에 장애물 $N$ 개가 놓여 있다. 장애물은 모두 코스 안의 선분이다. 장애물의 두께는 없고, 공과 홀은 점이다.

코스의 모양과 홀의 위치, 공의 출발 위치가 주어진다. 최대 한 번 튕기는 한 번의 샷으로 공을 홀에 넣을 수 있는지 판정하는 프로그램을 작성하시오. 공은 장애물 $N$ 개와 벽 4개 중 어디에든 튕길 수 있다. 단, 공은 어떤 장애물의 끝점에도 닿으면 안 된다. 장애물이든 벽이든 물체 두 개가 만나는 점에 공이 닿으면 물체 두 개를 맞힌 것으로 센다.

입력

첫째 줄에 정수 $N$ ( $0 \le N \le 1000$ ), $W$ ( $3 \le W \le 100$ ), $H$ ( $3 \le H \le 100$ )가 주어진다. $N$ 은 코스에 놓인 장애물의 개수, $W$ 는 코스의 너비, $H$ 는 코스의 높이다.

둘째 줄에 공의 좌표 $x$ ( $1 \le x < W$ )와 $y$ ( $1 \le y < H$ )가 주어진다.

셋째 줄에 홀의 좌표 $x$ ( $1 \le x < W$ )와 $y$ ( $1 \le y < H$ )가 주어진다.

다음 $N$ 개 줄에 장애물이 한 줄에 하나씩 주어진다. 각 줄에는 정수 $x_1$ ( $0 \le x_1 \le W$ ), $y_1$ ( $0 \le y_1 \le H$ ), $x_2$ ( $0 \le x_2 \le W$ ), $y_2$ ( $0 \le y_2 \le H$ )가 주어지며, $(x_1, y_1)$ 과 $(x_2, y_2)$ 를 끝점으로 하는 선분 장애물이 있다는 뜻이다. $(x_1, y_1) \ne (x_2, y_2)$ 임이 보장된다.

공과 홀의 위치는 서로 다르고, 둘 다 벽과 장애물 어디에도 닿아 있지 않다. 물체끼리는 서로 교차할 수 있지만, 두 물체가 겹치는 부분이 한 점을 넘지는 않는다.

출력

최대 한 번 튕겨서 공을 홀에 넣을 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

예제5

예제 1
입력
```
0 10 10
1 1
5 5
```
예상 출력
```
YES
```
예제 2
입력
```
1 10 10
1 1
9 9
1 9 9 1
```
예상 출력
```
NO
```
예제 3
입력
```
1 10 10
1 5
9 5
5 6 5 8
```
예상 출력
```
YES
```
예제 4
입력
```
2 20 4
1 2
19 2
0 1 20 1
0 3 20 3
```
예상 출력
```
YES
```
예제 5
입력
```
2 10 10
1 1
9 9
4 4 6 6
4 6 6 4
```
예상 출력
```
NO
```