Love Is...

Special Judge Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

      Jessie likes Jane. She is very beautiful, he likes to watch at her. But Jessie likes Jill as well. She is also very beautiful. When she is sitting at the bench and reading a book, Jessie is ready to watch at her for years. Why not come and talk? There is a problem. Jessie is a dog.
      But Jessie is not disappointed with the fact. Actually, he is quite used to it. But he really likes watching the girls. Unfortunately, there are many houses and other obstacles that try to break Jessie’s plans. So sometimes it is impossible to watch at both girls simultaneously. Sometimes it is possible, but it is always hard to find the apropriate point. Jessie asks you, his master, help him.
      Given the location of the obstacles and the points where the girls are, find the point from which both girls are visible, or find out that there is no such point. Of course, Jessie cannot get inside obstacles.

Input

      The first line of the input file contains two integer numbers x1 and y1— the coordinates of Jane. The second line contains x2 and y2— the coordinates of Jill. The third line of the input file contains n —the number of obstacles (0 ≤ n ≤ 10).
      All obstacles are rectangles with sides parallel to coordinate axis. The following n lines contain four integer numbers each xi,1, yi,1, xi,2 and yi,2— the coordinates of the bottom-left and top-right corners of the obstacles. All coordinates do not exceed 100 by their absolute value. Obstacles do not intersect but may touch each other. If two obstacles touch each other by corners, or sides there is no hole. In the other case Jessie can look so that his line of sight touches the corner or goes along the side of the obstacle.
      No girl is inside or on the border of any obstacle. Girls’ positions do not coincide.

Output

      If there is a point from which Jessie can see both girls, print “YES” at the first line of the output file. In this case the second line of the output file must contain two real numbers — the coordinates of the point from which Jessie must watch. The point must not be inside any obstacle, but may be on its border.
      Jessie must not be at the point that belongs simultaneously to two corners of the buildings that do not have a common side.
      The coordinates must be accurate up to at least 10-6.
      If there is no such point, print “NO” at the first line of the output file.

Sample Input

2 0
-2 0
1
-1 -2 1 2

2 0
-2 0
3
-1 -1 1 1
-3 -3 -1 -1
-3 1 1 3

Sample Output

YES
0.0 4.0
NO

Hint

单组数据,样例为前2组

Source

Andrew Stankevich Contest 16

Manager

Information
Solved Number1
Submit Number10
Problem Tags
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel