Statistics

Problem Statement for "LinePlotter"

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

  1. {"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.

  2. {"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.

  3. {"2663 942 8682 2917", "4195 2289 6894 4758", "1025 4423 6061 7827", "8135 1567 8331 950", "1228 3494 3808 8815", "7831 5360 8348 1641", "6944 5106 7894 6372", "2105 5440 9356 7700", "1097 878 7145 5980", "403 5544 8247 7563"}

    Returns: 62445

  4. {"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

  5. {"4131 7453 5297 9782", "3187 6001 9891 543"}

    Returns: 30158

  6. {"6685 9445 8449 4301"}

    Returns: 23038

  7. {"4787 6926 9271 6358", "3855 5861 8837 4091", "4287 4212 8337 7949", "2608 1184 3410 3550", "2444 9336 4832 5008", "1263 1072 1647 2472", "2182 7786 2596 7622", "4091 1635 4492 6998", "262 7492 610 9526", "582 2863 3983 8277", "1656 1086 7681 1594", "3124 8952 7559 9075", "1679 5556 5699 2448", "2506 71 7620 5057", "4260 8478 7345 9229"}

    Returns: 77015

  8. {"1289 7850 5030 9680", "4789 473 6271 9927", "7343 632 9526 7945", "134 4494 5944 8733", "1668 4551 3605 241"}

    Returns: 49403

  9. {"1076 7456 8432 8905", "2375 7146 5111 193", "5693 6621 6508 810", "2939 3806 3945 8737"}

    Returns: 42040

  10. {"6851 4575 7177 5147", "117 1388 2380 6569", "5643 3012 8011 8759", "1624 6442 3188 6367"}

    Returns: 28126

  11. {"1358 1135 1580 7233", "2311 6082 8342 8610", "1986 999 3874 7520", "6872 4336 8117 5095", "4910 392 9714 7082", "3945 3098 5289 4582", "711 7022 742 6534", "56 9765 4653 1710", "2332 423 8564 7249", "4410 5076 9520 9875", "4414 1794 6291 8677", "5063 6775 5271 1496"}

    Returns: 81883

  12. {"240 7647 2598 3992", "3678 9859 8406 1430", "7141 1082 7775 1198", "4614 2518 5482 2159"}

    Returns: 27920

  13. {"5778 8789 8410 7575", "6380 7657 9443 7855", "5754 9594 9938 9429", "5000 9282 8251 6499", "1028 1265 3749 9049", "1933 5377 8778 6749", "1986 7699 7732 6449", "6813 2628 7367 1616", "4378 2534 7785 2845", "5209 7415 8791 7776", "5129 4225 6572 2277", "98 6750 732 2558", "3831 5180 5106 3219", "151 8753 2395 1237", "4456 5521 6019 1340"}

    Returns: 83744

  14. {"4117 1701 9187 662", "3948 8352 5199 2903"}

    Returns: 26976

  15. {"699 45 2504 9457", "6219 6382 6799 9031", "7488 5534 8138 6214", "1394 6616 8406 5861", "2751 6267 8767 3671", "5873 7734 8583 5406", "920 2854 1444 580"}

    Returns: 43804

  16. {"1860 3055 7607 9008"}

    Returns: 18016

  17. {"665 4295 4452 4518", "5037 4299 8675 7842", "2157 3391 8689 7817", "7438 3313 9734 1015", "7312 5359 7730 9066", "5472 9558 9481 7237", "4424 8855 9235 9074"}

    Returns: 48850

  18. {"2687 5164 5235 6326"}

    Returns: 14038

  19. {"4020 8585 4245 5143", "3509 6695 5239 3224", "1233 4941 9915 7347", "3890 9790 7788 4395", "209 4052 8801 5453"}

    Returns: 46701

  20. {"634 2576 8212 7444", "6413 2197 9022 3055", "6844 2892 7327 5074", "3764 5733 4647 6659", "223 1666 1927 5597", "1520 3379 1953 3868", "7430 4608 9168 3519"}

    Returns: 33966

  21. {"1556 9936 6334 4236", "7121 4411 8004 2386"}

    Returns: 26452

  22. {"1559 5579 6975 3102", "2046 7228 9226 694", "947 5219 1054 1342", "4133 4742 5052 6052", "568 1019 6777 5487", "1253 3261 5543 4823", "7603 5704 8307 4915", "1481 8588 4027 9023", "4766 16 9971 2312", "530 4138 8234 3243", "406 1011 3505 5300"}

    Returns: 66842

  23. {"8453 4480 8996 6836", "2314 4180 3824 6869", "6640 899 7035 9153", "4253 9954 6663 2098", "4688 8247 9804 3008", "7693 164 9763 4979", "5311 5965 7559 7647", "1100 2259 5409 9247", "3851 9747 7383 9141", "1515 6928 8497 4162", "5573 6244 9286 6563", "3398 2108 6614 4555", "3393 5293 4098 664"}

    Returns: 82914

  24. {"4565 7933 8628 2238", "422 1265 6010 4521", "1614 3978 4729 7135", "6222 6299 8069 5704"}

    Returns: 27572

  25. {"2703 4911 9401 1130", "1146 7182 6677 1730", "2298 9122 2748 1082", "1213 7847 7883 4060", "6267 8183 7845 7717", "6195 5966 6540 902", "7403 8568 8134 3158", "1048 6546 9709 6448", "5072 3530 6147 5183", "241 4371 1640 7318"}

    Returns: 72141

  26. {"2683 4490 7348 8174", "602 8736 747 103", "4338 486 7620 2946", "4171 3191 8581 3005", "4388 309 8898 6487", "4028 4748 7230 5446", "4740 9966 8257 2679", "5850 4986 7533 8392", "7426 7706 8649 1500", "285 4790 5733 3325"}

    Returns: 70972

  27. {"153 4976 3865 3272", "1483 1960 6788 3355", "8987 1857 9584 6906", "1874 7994 6946 1517", "3483 2506 6483 1455"}

    Returns: 40214

  28. {"3965 6687 6134 8595", "3448 7071 3626 9635", "5921 2869 9911 6884", "2066 8056 4453 6714", "510 7059 6756 8004"}

    Returns: 38080

  29. {"3347 1078 4015 220", "3301 5660 9906 7866", "4526 1073 4910 3919", "164 7634 3106 1137", "1987 9936 6317 9327", "5486 9830 9984 4579", "6120 2657 8854 9795", "931 5166 6103 4382", "6981 9251 7071 8524", "6236 330 8831 7592", "1096 8490 8439 5623", "2441 2462 9852 5617"}

    Returns: 84433

  30. {"2424 2990 6924 2745", "6801 9746 9613 8992"}

    Returns: 26295

  31. {"2757 372 8554 8990", "9330 122 9389 3654", "2471 3505 2556 6700", "5575 3213 6552 2072", "4680 3367 8281 4646", "3338 6377 5171 8256"}

    Returns: 40558

  32. {"1927 6868 7526 6404", "315 4594 8132 9655", "6885 2051 8565 1212", "5524 2376 8919 4667", "1555 5768 4514 4156", "6037 1829 6933 9132"}

    Returns: 45786

  33. {"3900 3066 9299 578", "13 7664 6202 2243", "1195 1742 5847 8391", "198 6525 2635 2803", "1032 7383 4170 5946", "3503 8246 8735 9442", "6074 4312 7961 8404"}

    Returns: 51330

  34. {"43 8673 362 9422", "3475 3016 8162 7322", "2278 7898 9904 258", "1054 7623 9199 8735", "1643 3171 4273 606", "2801 2860 6023 2999", "6068 2539 7481 9430", "2990 8392 8992 5848", "273 2379 1614 9946", "5808 2513 9508 364", "962 9509 5418 1797"}

    Returns: 78311

  35. {"2233 3712 9347 7877", "3386 5849 6656 4331", "3497 3969 4413 1586", "116 627 3386 3076", "3902 8582 4832 946", "3533 4032 5205 7046", "2150 3150 5023 9890", "5025 415 7466 601"}

    Returns: 51118

  36. {"46 8914 3742 8999", "1468 2301 2532 8806", "8098 9882 9770 7130", "135 7596 4116 4708", "4175 9909 7585 7563", "3615 3938 8946 3035", "5507 7871 8510 1517"}

    Returns: 50888

  37. {"2523 445 4488 5413", "4553 9838 8152 6015", "4845 23 6723 8930", "6802 8554 6898 1732", "169 1012 5481 6743", "1543 6839 4524 8503"}

    Returns: 47826

  38. {"4101 6296 8897 1215", "2596 7167 6529 6912"}

    Returns: 26328

  39. {"7149 5153 7447 5723", "612 4773 4698 2352", "5747 9979 9667 3692", "5035 7364 5146 4834", "3591 2911 4354 7159", "957 7917 7205 9936", "9766 8936 9992 9233", "3712 3532 6711 4326", "7382 6915 8984 45"}

    Returns: 59438

  40. {"2361 7811 8499 2701", "3168 5925 9051 3564", "151 5621 8903 1849", "4725 3330 7897 974", "1035 191 7173 8799", "3769 4986 6245 9276", "718 3617 8414 8315", "180 4873 3078 5556", "6255 4478 9932 7944", "6860 9608 9466 4495", "1415 9877 7897 1019", "989 9142 6577 4634", "1471 8737 5495 3998", "1782 3439 7598 9692"}

    Returns: 97028

  41. {"5837 9811 7145 6043", "4190 4318 5760 4012", "235 772 7754 1877", "598 4632 1276 1836", "2823 2941 8125 9046"}

    Returns: 33969

  42. {"3338 7266 7777 1546", "5184 6066 5258 3789", "712 228 5120 8652", "8568 432 9089 6899", "1206 9916 3576 6529", "2901 7165 8654 3265", "2550 9294 5724 3051", "2622 6477 8623 5081", "905 2253 9371 5264", "4720 9903 9631 7061", "5745 5402 8221 2755", "1521 283 2974 8104"}

    Returns: 83265

  43. {"2496 3330 3232 825", "3065 7410 8052 293", "4687 2416 7681 9398", "1741 4079 3833 5739", "367 392 5072 8173"}

    Returns: 38501

  44. {"6625 4299 7852 3111", "5597 1499 6300 3044", "6705 3871 8968 7576", "5701 5415 6680 8767", "691 9386 6812 1952", "7597 416 8614 8558", "435 9804 3069 6183", "1069 483 2637 4393", "656 4901 9064 9151", "4865 1633 5437 2681", "8669 1890 9300 932", "2946 4556 9028 9932", "6064 215 6739 8401"}

    Returns: 76505

  45. {"6832 6171 9459 7920", "2031 1898 6093 6097", "3051 8586 6041 9501", "1660 8948 7625 8131", "3855 9135 9213 529", "7556 5867 9719 579", "5674 5957 7967 6253", "2053 6477 9820 622", "2335 7533 4527 4515", "7917 7638 8307 7583", "809 2925 3048 6039", "2510 813 3908 4122"}

    Returns: 71195

  46. {"4056 7881 9211 9460", "2745 6427 7815 6358", "3626 2907 5700 1954", "198 888 7861 7274", "2505 3705 4254 9063", "2816 6145 8157 3550", "764 5624 2910 8883"}

    Returns: 49985

  47. {"1949 5762 8450 7696", "6865 7341 7395 8738", "4494 9638 4590 3764"}

    Returns: 27550

  48. {"1545 8643 7359 9347", "4539 6971 5000 5701", "3400 8500 7742 7868", "4274 7601 5646 3331", "2838 9626 6899 3649", "839 1297 6115 9467", "982 9468 5039 8770", "5682 9284 8184 6114", "5740 4301 6296 5033", "7003 6852 9302 2044", "223 8106 9241 334", "658 3826 9208 9898", "3547 7717 3615 8348"}

    Returns: 80512

  49. {"6437 7615 8339 3881", "1548 6557 5955 863", "3335 8872 7307 9164", "4369 9117 9197 2454", "1036 4722 1424 3575", "7297 147 8823 7782", "5817 6610 6756 5644", "9029 3380 9084 6673"}

    Returns: 52847

  50. {"6291 6439 6714 8036", "1491 9289 6717 6886", "8821 827 9215 2967", "2969 5963 6290 4548", "5418 8613 8887 7019", "180 7199 928 447", "215 6332 4401 7201", "476 3703 9028 580"}

    Returns: 51271

  51. {"393 3690 4773 6203", "1264 2385 1667 1487", "6312 1209 8173 4529", "7452 6691 8106 4224", "5303 9285 6703 5976", "2068 3812 9697 5616", "3590 5546 4879 6074", "1684 6137 9304 6907", "9410 3547 9639 3111", "3433 9157 8682 9102", "4035 9887 8242 4077", "2919 2260 3991 9943", "1372 3531 2535 4549", "103 1932 5327 7890", "3301 4694 4460 4789"}

    Returns: 80295

  52. {"6212 9121 8124 2911", "6469 1225 8008 2806", "2196 9037 9520 1430", "5042 9884 9088 5952", "8212 2543 9385 7258", "5092 1914 9326 9238", "1102 1301 1172 4036", "7356 3423 7630 6705", "1996 3430 4889 8983", "1035 7716 1183 609", "1722 2766 3837 8639", "2357 3732 3856 2180", "3315 6251 9783 9961", "1474 9105 5068 9122", "819 9812 4281 5873"}

    Returns: 89835

  53. { "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

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: