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: Driving Directions
Description Contrary to the popular belief, alien flying saucers cannot fly arbitrarily around our planet Earth. Their touch down and take off maneuvers are extremely energy consuming, so they carefully plan their mission to Earth to touch down in one particular place, then hover above the ground carrying out their mission, then take off. It was all so easy when human civilization was in its infancy, since flying saucers can hover above all the trees and building, and their shortest path from one mission point to the other was usually a simple straight line — the most efficient way to travel. However, modern cities have so tall skyscrapers that flying saucers cannot hover above them and the task of navigating modern city became quite a complex one. You were hired by an alien spy to write a piece of software that will ultimately give flying saucers driving directions throughout the city. As your first assignment (to prove your worth to your alien masters) you should write a program that computes the shortest distance for a flying saucer from one point to another. This program will be used by aliens as an aid in planning of mission energy requirements. The problem is simplified by several facts. First of all, since flying saucer can hover above most of the buildings, you are only concerned with locations of skyscrapers. Second, the problem is actually two-dimensional — you can look at everything “from above” and pretend that all objects are situated on By definition, the location of flying saucer is the location of its center, and the length of the path it travels is the length of the path its center travels. During its mission flying saucer can touch skyscrapers but it cannot intersect them. At the first picture a flying saucer of In the second picture it is impossible for a flying saucer of In the third picture flying saucer of Input The first line of the input file contains integer numbers y, _{A}x, and _{B}y (−1000 ≤ _{B}x, _{A}y, _{A}x, _{B}y ≤ 1000), where (_{B}x, _{A}y) are the coordinates of the starting point of the flying saucer’s mission and (_{A}x, _{B}y) are the coordinates of its finishing point. The following _{B}n lines describe skyscrapers. Each skyscraper is represented by four integer numbers x_{1}, y_{1}, x_{2}, and y_{2} (−1000 ≤ x_{1}, y_{1}, x_{2}, y_{2} ≤ 1000, x_{1} < x_{2}, y_{1} < y_{2}) — coordinates of the corners of the corresponding rectangle.Skyscrapers neither intersect nor touch each other. Starting and finishing points of the flying saucer’s mission are valid locations for flying saucer, that is, it does not intersect any skyscraper in those points, but may touch some of them. Output Write to the output file text “ Sample Input
Sample Output
Source |

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

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

Any problem, Please Contact Administrator