|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|5 초||512 MB||15||1||1||33.333%|
Everyone loves mini-golf! The aim of the game is to hit a ball from a starting location into a hole, possibly bouncing off objects on the way.
You would like to get some more practice in, so you are going to write a computer program that will help you. You need to figure out whether you can get the ball in the hole with just one shot. Since you are still an amateur, you are only comfortable taking a shot that will bounce off at most one object before landing in the hole. The course is a rectangle with N obstacles on it, each of which are straight line segments in the course. You may assume that the obstacles are infinitely thin and the ball and hole are points.
Given a description of the course, the location of the hole and the starting location of the ball, you need to determine whether or not it is possible to get the ball into the hole in one shot such that the ball bounces at most once. The ball can bounce off any of the N obstacles or the 4 walls. However, the ball may not touch the endpoint of any obstacle. Note that if the ball touches the intersection of two objects (either obstacles or walls), then this will count as hitting two objects.
The first line of input contains three integers N (0 ≤ N ≤ 1 000), which is the number of obstacles on the course, W (3 ≤ W ≤ 100), which is the width of the course, and H (3 ≤ H ≤ 100), which is the height of the course.
The second line describes the ball. This line contains two integers x (1 ≤ x < W) and y (1 ≤ y < H), which are the coordinates of the ball.
The third line describes the hole. This line contains two integers x (1 ≤ x < W) and y (1 ≤ y < H), which are the coordinates of the hole.
The next N lines describe the obstacles. Each of these lines contains four integers x1 (0 ≤ x1 ≤ W), y1 (0 ≤ y1 ≤ H), x2 (0 ≤ x2 ≤ W) and y2 (0 ≤ y2 ≤ H), which indicates that there is an obstacle that is a straight line with endpoints (x1, y1) and (x2, y2). It is guaranteed that (x1, y1) ≠ (x2, y2).
The ball and the hole will be at distinct locations and will not be touching any object (wall or obstacle). It is possible that the objects (obstacles and walls) intersect each other. However, they will not overlap at more than one point.
If it is possible to get the ball into the hole with at most one bounce, display YES. Otherwise, display NO.
0 10 10 1 1 5 5
1 10 10 1 1 9 9 1 9 9 1
1 10 10 1 5 9 5 5 6 5 8
2 20 4 1 2 19 2 0 1 20 1 0 3 20 3
2 10 10 1 1 9 9 4 4 6 6 4 6 6 4