TopCoder problem "LinePlotter" used in TCO04 Round 2 (Division I Level Two)



Problem Statement

    

On a plotter, the mechanical arm that draws on paper with a pen has a motor that can move it back and forth across the paper sideways. The plotter also has a paper motor, which can move the paper orthogonally to the plotter's arm, which effectively is like moving the pen up and down the paper. The paper is square, and is oriented so its lower edge is parallel to the arm. This allows the plotter to move to any coordinates using the two motors. Both motors can be active simultaneously, and each motor can move the pen up to one pixel per millisecond in relation to the paper (it's possible for a motor to run slower).

Given the list of lines that the plotter must put on the paper, return the minimum time it takes to plot the given lines, in milliseconds. The plotter's pen starts at the coordinates (0,0), and after drawing all the lines, must return to (0,0). Note that the plotter cannot draw partial lines. Each element of lines will be in the form "x1 y1 x2 y2". This represents a line from point (x1,y1) to point (x2,y2). It takes 0 time to lower the pen down on the paper, and to raise it off the paper.

 

Definition

    
Class:LinePlotter
Method:timeToPlot
Parameters:String[]
Returns:int
Method signature:int timeToPlot(String[] lines)
(be sure your method is public)
    
 

Notes

-There can be 0-length lines, which are drawn by moving to the designated location, lowering the pen and without moving, raising the pen.
 

Constraints

-lines will contain between 1 and 15 elements, inclusive.
-Each element of lines will be of the form "x1 y1 x2 y2", where each value is an integer between 0 and 9999, inclusive.
-There will be no extra leading zeros in any of the numbers in lines.
-There will be no repeated elements in lines. This includes lines which are reversed. For example, if "x1 y1 x2 y2" appears, then "x2 y2 x1 y1" cannot.
-No two lines can intersect at more than one point.
 

Examples

0)
    
{"0 1 1 0"}
Returns: 3
This is a line which draws a diagonal across the bottom corner of the paper. The line can be drawn by first running the arm motor to bring the pen over to (1,0) in 1 millisecond. Then the paper motor can be run simultaneously with the lateral motor to draw the line from (1,0) to (0,1) in one more millisecond. Finally, the paper motor brings the pen back to (0,0) in one more millisecond.
1)
    
{"0 0 5 5", "5 5 0 5", "0 100 0 4"}
Returns: 205
The best path first draws the line from (0,0) to (5,5). Since both motors can move at top speed, this line takes 5 milliseconds to draw. Without even picking up the pen, we can draw the line from (5,5) to (0,5) in 5 milliseconds. Finally, to draw the final line, we lift the pen, go all the way up to (0,100), and draw the line to (0,4). This adds 95 + 96 = 191 milliseconds. Finally, we lift the pen and move back to (0,0), adding an additional 4 milliseconds. The total time is 5 + 5 + 95 + 96 + 4 = 205 milliseconds.
2)
    
{"4647 8139 5695 458", "346 6987 5003 8789", "4955 4552 8216 4667",
 "1676 5564 9137 703", "2722 911 3594 2734", "1718 6222 4828 6335",
 "1265 5243 3677 2489", "2809 718 6675 9926", "5626 9254 8843 2486",
 "4938 6286 9083 1621", "2058 9050 3421 6083", "1648 1890 6058 2896",
 "6598 6029 8159 4543", "1279 634 5472 6714", "2295 4885 9765 5706"}
Returns: 92635

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=2364

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=5879&pm=2364

Writer:

schveiguy

Testers:

PabloGilberto , lbackstrom , vorthys

Problem categories:

Brute Force, Dynamic Programming, Geometry, Graph Theory, Search, String Parsing