FAKETSP - Traveling Salesman
According to Wikipedia, "The Traveling Salesman Problem (TSP) is a problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest possible tour that visits each city exactly once. The problem was first formulated as a mathematical problem in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved."
Fortunately, you won't have to solve TSP. You're working for a very clever traveling salesman who has already figured out the path he is going to take. All he needs from you is a quick way to figure out how far he traveled after every segment of his tour.
Input
The salesman kept detailed records of his travels. You'll be getting a series of lines of the form "Some text (X, Y)." indicating that the salesman has been at the point X kilometers east and Y kilometers north of the origin of a Cartesian plane.
Output
For each segment of the trip, output the total distance traveled up to that point as a line in the format "The salesman has traveled a total of D kilometers." Show three digits after the decimal point when printing D. Note that the salesman only travels in straight lines (even after a couple of drinks).
Example
Input: I started out at (0, 5). Then I traveled to (3.7, 5). After a couple of drinks I wobbled to (2.7, 4). The next morning I woke up near (4, 3). I finished my journey in (-.2, 8). Output: The salesman has traveled a total of 3.700 kilometers. The salesman has traveled a total of 5.114 kilometers. The salesman has traveled a total of 6.754 kilometers. The salesman has traveled a total of 13.284 kilometers.
hide comments
vas14:
2022-02-28 02:46:26
Looks like the input contains an empty line at the end |
|
minhthai:
2016-02-12 08:13:53
when reading the input is harder than solving the problem :) |
|
Shivam Singh:
2015-07-05 07:15:31
The only interesting thing in this problem is to take inputs, switching between characters and doubles, rest is really easy. |
|
Arafat dad Khan:
2015-05-24 05:22:27
Change float to double to get AC!! |
|
Rishav Goyal:
2014-02-06 15:25:53
ideone giving wrong ans (_-_) (--_--)
|
|
Martijn Muijsers:
2013-11-28 02:08:29
quit your program when you find a character c that is EOF (C/C++). Other ways of terminating input didn't work for me, incl. scanf(..)==.. and feof. I kept getting timelimit exceeded, even with getchar_unlocked() :P Last edit: 2013-11-28 02:08:56 |
|
BLANKRK:
2013-07-12 10:16:17
nice problm....enjoyd solving this....spaclly taking these kind of inputs....:D |
|
Syntax Terror:
2013-06-30 08:30:39
Anything wrong with my submission? I guess its working for all cases wich i tried!. ID:9577734 using PHP |
|
ɥsǝןǝǝu:
2013-01-30 06:40:54
only one '(' and , ')' in a line
|
Added by: | Miorel Palii |
Date: | 2009-10-15 |
Time limit: | 1s |
Source limit: | 4096B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 C++ 4.3.2 ERL NODEJS OBJC PERL6 SQLITE VB.NET |
Resource: | University of Florida Team Practice 2009 |