El lunes, 5 de noviembre de 2012 03:01:00 UTC-3, Sanjeet Roy escribió: > > Assume a Taxicab is located at the origin (0,0) in the below Grid. The > hori- > zontal and vertical lines in the Grid is the road on which his taxi can > move. If > the cab wants to move to a place, say (3,4), the distance the cab has to > travel > is (3 - 0) + (4 - 0) = 7 units. The distance calculated in this way is > called Man- > hattan distance. In general, Manhattan distance between two points (x1 , > y1 ) > and (x2 , y2 ) is calculated as |x2 - x1 | + |y2 - y1 |. As you must be > aware, the > Eucledian distance between the same two points is calculated as > (x2 - x1 )2 + (y2 - y1 )2 > 3 > Figure 1: Manhattan distance > Given n points to the taxicab driver located at a position (x,y), he/she > has to > arrange the points in the order of increasing manhattan distance. For > example, > If (3,4), (5,3) and (2,2) are the points given to the cab driver who is at > the > postion (1,1), then the driver will output (2,2), (3,4) and (5,3) as these > points > are in the order of increasing distance from the Taxicab position (1,1). > You are required to write a program to help the driver. The input is of the > following format: > * The first line will contain the position of the Taxicab. For example, the > position could be ((3,0)). > * Next line will contain the number of points. For your program 2 <= n <= > 100 > * Next n lines will contain the points with each point on a new line. > After reading the input, your program should calculate Manhattan distance > from the Taxicab position and arrange the points in the order of increasing > Manhattan distance. Each point should be printed in a new line. If > Manhattan > distance is equal for two points, first output the point that has the > least x co- > ordinate. > For Example: > INPUT > (2,0) > 4 > (3,4) > 4 > (0,1) > (6,7) > (2,3) > OUTPUT > (0,1) > (2,3) > (3,4) > (6,7) >
NetworkX [1]. Es much more than what you need. [1] http://networkx.lanl.gov/ --
