Hello everyone! i found some days ago a really nice algorithmic problem, and i am trying to solve it (implement it in pascal in the end).
I know it is a shortest path problem, (it is obvious) but i still can't seem to find any proper approach to it!
Any help (thoughts..) will be appreciated!
So here is the problem:
We have a mail man that is trying to deliver mails to some ports between his home and his office.
The home of the mail man, is at the point (0,0) (cartesian coordinates), and the office at the point (A,B).
In between there are the ports with coordinates X,Y.
The mail man though can do only 2 routes. One in the morning, from home to office and one in the evening from office to home. He must deliver all mails in those 2 routes.
Yet, in the morning route, he can visit only the ports which have a greater x-coordinate than his previous location, and in the evening route he can visit ports with smaller x-coordinate than his previous location.
We should make a program that calculates the minimum distance he must travel, to deliver mails to all the ports.
Input File:
First line contains an integer N, 0<N<=200, the numbers of the port.
second line contains two integers A,B , 1<=A,B<=1000 , the coordinates of the office.
The following N lines contain, the coordinates of the ports X,Y , 1<X<=A and -1000<=Y<=1000.
All coordinates are seperated with space.
OUtput: An integer, the minimun distance.
Please request clarifications if needed.