N개의 선분 장애물과 네 벽 중 하나에 최대 한 번 튕겨 공이 홀에 들어갈 수 있는지 판정한다.
보통7기하완전 탐색구현아직 제출이 없습니다시간 제한5초메모리 제한512 MB미니골프는 출발 위치에 놓인 공을 쳐서 홀에 넣는 경기다. 가는 길에 물체에 튕겨도 된다.
연습을 더 하려고 컴퓨터 프로그램을 만든다. 이 프로그램은 한 번의 샷으로 공을 홀에 넣을 수 있는지 판정한다. 아직 초보라서 홀에 들어가기 전에 최대 한 번만 튕기는 샷만 친다.
코스는 직사각형이고 그 안에 장애물 N개가 놓여 있다. 장애물은 모두 코스 안의 선분이다. 장애물의 두께는 없고, 공과 홀은 점이다.
코스의 모양과 홀의 위치, 공의 출발 위치가 주어진다. 최대 한 번 튕기는 한 번의 샷으로 공을 홀에 넣을 수 있는지 판정하는 프로그램을 작성하시오. 공은 장애물 N개와 벽 4개 중 어디에든 튕길 수 있다. 단, 공은 어떤 장애물의 끝점에도 닿으면 안 된다. 장애물이든 벽이든 물체 두 개가 만나는 점에 공이 닿으면 물체 두 개를 맞힌 것으로 센다.
첫째 줄에 정수 N (0≤N≤1000), W (3≤W≤100), H (3≤H≤100)가 주어진다. N은 코스에 놓인 장애물의 개수, W는 코스의 너비, H는 코스의 높이다.
둘째 줄에 공의 좌표 x (1≤x<W)와 y (1≤y<H)가 주어진다.
셋째 줄에 홀의 좌표 x (1≤x<W)와 y (1≤y<H)가 주어진다.
다음 N개 줄에 장애물이 한 줄에 하나씩 주어진다. 각 줄에는 정수 x1 (0≤x1≤W), y1 (0≤y1≤H), x2 (0≤x2≤W), y2 (0≤y2≤H)가 주어지며, (x1,y1)과 (x2,y2)를 끝점으로 하는 선분 장애물이 있다는 뜻이다. (x1,y1)=(x2,y2)임이 보장된다.
공과 홀의 위치는 서로 다르고, 둘 다 벽과 장애물 어디에도 닿아 있지 않다. 물체끼리는 서로 교차할 수 있지만, 두 물체가 겹치는 부분이 한 점을 넘지는 않는다.
최대 한 번 튕겨서 공을 홀에 넣을 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.