Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: ACM Underground
Description ACM is a town with a very special underground metro system which consists of a set of railway segments, each is called a line. There are trains in both directions of each line. Two lines may intersect which allows a passenger to switch from one train in the first line to another train in the second line on that intersection. The source and destination of your travel lie somewhere on the metro lines. You start using the metro line where the source is located on and may change your line only at the intersection points between two metro lines, and continue until your reach the destination. Your goal is to make your travel free of charge; i.e., without the need to buy any tickets. The problem is that there are a number of policemen who check your tickets. Obviously, you do not want to confront with any of these policemen during your travel. You may confront policemen in two situations: either on an intersection, but only when you are changing your line, or when you are traveling along a line in which a policeman indiscriminately asks for everyone's tickets that are inside that wagon, including you. You know the locations of all policemen in advance. Note that if a police is located on an intersection, he asks for your ticket only if you want to change your line on that intersection, and if a police is located on a line (but not on an intersection), he will ask for your ticket if you are passing that location. In your map, there are some policemen in other locations, not on any metro lines, which you must ignore. For example, in the following figure, there are five metro lines, with three policemen located at black circles. You may travel from In this problem, you must write a program that reads the metro line specifications, the police locations, and your source and destination, and determine whether it is possible to travel from the given source to the given destination without meeting any policeman. Input The first number in the input line, y _{s}x _{d}y which are the coordinates of the source and the destination points respectively. You may assume these two points lie on metro lines. Following the second line, there are _{d}n lines of the form x _{1}y_{1} x_{2} y_{2} describing the metro lines where (x_{1}, y_{1}) and (x_{2}, y_{2}) specify the endpoints of the metro line. After this, there are m lines each containing a pair of integers x y that specify the location of a policeman. All coordinates are arbitrary integer numbers.Output The output contains Sample Input 2 4 2 3 2 5 8 3 2 3 6 8 1 5 8 7 7 2 2 9 2 1 6 3 4 6 6 3 2 2 3 6 3 1 3 7 3 3 2 3 6 1 5 7 2 3 4 4 3 Sample Output YES NO Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator