Statistics

Problem Statement for "SpiralConstruction"

Problem Statement

Given a set of points, choose the maximal number of them that can be used to form a spiral.

A spiral is formed as follows:

1. Start at point (0, 0).
2. Draw a line segment from the current point to one of the given points (x, y). (x, y) is now the new current point.
3. Repeat step 2 as many times as possible while obeying the following rules:
  • The spiral must not intersect itself. This means that no two line segments in the spiral can have any common points (except the common endpoints of neighboring segments).
  • Each point must not be used more than once.
  • When going from each line segment to the next, you must turn counterclockwise and go forward. The angle you turn must be greater than or equal to 0, and strictly less than 180 degrees.
  • The ray that originates from the second to last point and goes through the last point must not intersect any of the other line segments in the spiral.


These three spirals do not satisfy the first, second and third rules:

These two do not satisfy the fourth rule:


You are given a String[] points, each element of which represents a single point whose coordinates are given as "X Y" (quotes for clarity). Return the maximal number of points that can be used to form a single spiral.

Definition

Class:
SpiralConstruction
Method:
longestSpiral
Parameters:
String[]
Returns:
int
Method signature:
int longestSpiral(String[] points)
(be sure your method is public)

Constraints

  • points will contain between 1 and 15 elements, inclusive.
  • Each element of points will be formatted as "X Y" (quotes for clarity), where X and Y are integers with no extra leading zeros.
  • Each X and Y will be between -1000 and 1000, inclusive.
  • All elements in points will be distinct.
  • There will be no "0 0" in points.

Examples

  1. {"0 1", "1 0"}

    Returns: 2

    (0,0) -> (1,0) -> (0,1) is a valid spiral.

  2. {"1 1", "2 2", "-1 -1"}

    Returns: 2

    (0,0) -> (1,1) -> (2,2) is the longest valid spiral. Note that there is a turn by 0 degrees.

  3. {"0 1", "2 2", "-2 2", "-2 -2", "2 -2", "1 1"}

    Returns: 6

  4. {"0 1", "1 1", "0 2"}

    Returns: 2

    You can't form a valid spiral using all three points.

  5. {"4 -2", "2 2", "-5 6", "-7 8", "-9 -1", "3 0", "8 8", "-2 -4", "-4 -7", "-4 -1", "-1 -9", "-5 3", "4 9", "2 6", "-2 5"}

    Returns: 15

  6. {"5 1", "0 -6", "8 -8", "-9 4", "-1 0", "9 4", "5 0", "-4 4", "-1 9", "6 6", "2 6", "-1 -4", "-7 1", "4 -3", "-4 -8"}

    Returns: 15

  7. {"7 5", "4 9", "6 7", "-4 8", "7 7", "2 8", "7 8", "-2 3", "-2 -3", "9 6", "-3 5", "4 3", "-1 1", "-2 -1"}

    Returns: 11

  8. { "564 564", "952 952", "52 52", "625 625", "881 881", "130 130", "84 84", "715 715", "650 650", "150 150", "451 451", "474 474", "49 49", "572 572", "877 877" }

    Returns: 15

  9. { "1 1", "2 2", "3 3", "4 4", "5 5", "6 6", "7 7", "8 8", "9 9", "10 10", "11 11", "12 12", "13 13", "14 14", "15 15" }

    Returns: 15

  10. { "-9 0", "-8 5", "-3 -8", "7 3", "9 -1", "-1 0", "1 0", "-5 10", "-6 -4" }

    Returns: 8

  11. { "-2 -5", "4 2", "0 3", "-1 -4", "1 0", "-2 2", "4 -1", "5 3", "-2 3", "-2 -4" }

    Returns: 9

  12. { "-5 -4", "0 -4", "4 1", "0 1", "5 4", "2 -5", "0 2" }

    Returns: 6

  13. { "2 5", "-2 -5", "4 -5", "-5 -5", "2 4", "-1 -2" }

    Returns: 5

  14. {"0 1", "-1 0", "0 -1", "1 2", "2 -2", "-2 1", "1 0", "-1 -1", "1 3", "-3 -2"}

    Returns: 10

  15. {"-324 556", "-297 568", "799 -834", "708 793", "34 -181", "267 -44", "-33 757", "867 308", "-674 -103", "-156 -273", "-54 -516", "-396 573", "307 27", "-879 682", "-918 218"}

    Returns: 15

  16. {"-630 776","358 932","440 896","-999 -42","-985 169","-418 -908","-515 856","-817 -576","982 181","-255 -967","996 65","908 -417","10 -999","-566 -824","760 -649"}

    Returns: 15

  17. {"1 1","2 2","3 3","4 4","5 5","6 6","7 7","-1 -1","-2 -2","-3 -3","-4 -4","-5 -5","-6 -6","-7 -7","-8 -8"}

    Returns: 8

  18. {"1 1","2 2","3 3","4 4","5 5","6 6","7 7","8 8","9 9","10 10","11 11","12 12","13 13","14 14","15 15"}}

    Returns: 15

  19. {"-10 -10","10 -10","0 10","-20 -20","20 -20","0 20","-30 -30","30 -30","0 30","-40 -40","40 -40","0 40","-50 -50","50 -50","0 50"}

    Returns: 15

  20. {"-459 -33","-166 0","-331 224","-22 -142","462 -36","205 -355","-219 327","461 -9","495 442","327 -64","-109 104","402 -347","-208 -118","-79 216","218 395"}

    Returns: 15

  21. {"-9 17","-16 -50","19 -26","28 8","12 14","-45 -5","31 -23","11 41","45 -8","-23 -14","41 -46","-48 3","42 32","-29 -34","-32 45"}

    Returns: 15

  22. {"-4 2","-1 -5","4 -1","3 3","-3 -1","-4 -4","0 -3","2 1","-4 -1","-3 -2","-3 -3","-4 1","3 0","-4 3","4 -3"}

    Returns: 15

  23. {"1 7","4 0","9 4","8 8","2 4","5 5","1 1","5 2","7 6","1 4","2 3","2 2","1 6","8 5","1 8"}

    Returns: 6

  24. {"0 1", "0 3", "0 5", "0 2", "0 7"}

    Returns: 5

  25. {"0 1", "0 13", "0 15", "0 2", "0 17", "0 11", "0 3", "0 5", "0 12", "0 7", "0 123", "0 124", "0 231", "0 8", "0 99"}}

    Returns: 15

  26. {"0 1", "0 2", "0 3", "0 4", "0 5", "0 6", "0 7", "0 8", "0 9", "0 10", "0 11", "0 12", "0 13", "0 14", "0 15"}

    Returns: 15

  27. {"-669 -542", "160 -513", "473 717", "-51 344", "703 -548", "270 -869", "957 -181", "-6 -509", "-175 937", "-625 434", "901 -403", "-708 -847"}

    Returns: 12

  28. {"-293 413", "886 709", "716 445", "533 -236", "903 869", "-714 655", "890 27", "800 -311"}

    Returns: 5

  29. {"665 -682", "134 -338", "-761 708"}

    Returns: 3

  30. {"631 535", "-259 -354", "-147 -973", "737 -281", "-222 516", "34 -690", "842 -821", "-909 -712", "-62 36", "-363 255", "794 433", "-274 883", "343 -642", "86 -1"}

    Returns: 14

  31. {"620 547", "-928 -383", "-253 945", "-36 835"}

    Returns: 3

  32. {"-705 925", "-577 -64", "318 -386", "528 535", "-919 -890", "-467 -82", "100 -169", "644 -363", "926 -307", "-695 971", "-625 658", "-269 19"}

    Returns: 10

  33. {"-733 63", "-236 827", "95 566", "975 -496", "157 284", "-656 -373", "644 -245", "-971 567", "337 -954", "-67 150", "960 714", "92 429", "999 -824", "450 332", "740 -719"}

    Returns: 13

  34. {"-95 -62", "754 -807", "-421 -791", "-66 -581"}

    Returns: 3

  35. {"-595 24", "-100 154", "-247 -425", "402 655", "611 -644", "538 -473", "582 -520", "601 -961", "-714 -662", "370 -179", "-406 15", "335 -991"}

    Returns: 12

  36. {"-528 659", "-268 -723", "999 -947", "925 -595", "787 -103", "-533 -882", "-114 727", "-528 -364", "-580 799", "-386 -697"}

    Returns: 10

  37. {"-698 510", "-74 613", "-410 443", "-489 247", "-213 541", "-779 -712", "842 3", "-18 -407", "194 -314", "92 -525", "-492 -664", "300 587", "445 499", "452 188"}

    Returns: 14

  38. {"787 -430", "274 -209", "-212 580", "144 996"}

    Returns: 4

  39. {"-471 611", "-965 -714", "-819 -833", "955 643", "806 -812", "147 -123", "-806 506", "-740 -367", "-682 -955", "-651 -365", "-134 -116", "855 -581", "833 -868"}

    Returns: 10

  40. {"983 871", "-358 -683", "697 -984", "-538 556", "-623 879", "-293 73", "-491 -401"}

    Returns: 7

  41. {"853 -144", "395 -319", "248 785", "0 -585"}

    Returns: 3

  42. {"-720 -830", "411 75", "746 -397", "-83 828", "-847 -833", "181 709", "314 967", "-322 -633", "-450 415", "-459 433", "508 438"}

    Returns: 11

  43. {"708 -949", "-869 752", "-729 -583", "-321 984", "-462 -477", "857 429", "-807 -57", "296 184", "-728 -594", "-524 -903", "-551 -726"}

    Returns: 10

  44. {"696 -895", "-339 301", "-743 784", "-657 -689", "-957 170", "-197 -88", "-65 832", "743 -689", "549 -693", "969 635"}

    Returns: 10

  45. {"185 -858", "126 -788"}

    Returns: 2

  46. {"-560 533", "-539 168"}

    Returns: 2

  47. {"-721 649", "245 -574", "-859 -986", "-257 496", "180 -361", "-528 -691", "-833 -992", "-222 -989", "950 901", "-803 388", "-536 624", "310 -588", "320 812", "-640 862", "828 -851"}

    Returns: 14

  48. {"-717 484", "-827 515", "-746 765", "-333 763", "979 184", "-524 101"}

    Returns: 5

  49. {"-200 624", "-488 -903", "543 -376", "18 924", "55 958", "-12 -826", "497 419", "-286 580", "-512 25"}

    Returns: 9

  50. {"271 214", "897 58", "-644 178", "-41 -598", "156 -737", "-182 -765", "748 702", "-335 -113"}

    Returns: 8

  51. {"-860 -456", "-306 688", "-995 614", "-437 -876", "-353 684", "363 -711", "-324 -545", "840 -418", "18 472", "109 -550", "-201 141"}

    Returns: 11

  52. {"1 -1", "-3 -3", "1 -2", "2 1", "0 2", "-4 -2", "-3 -4", "1 -3", "3 0", "1 3", "-3 1", "-5 -3", "-3 -5", "4 -2", "3 1" }

    Returns: 14

  53. {"0 1", "0 2", "0 3", "1 0", "1 1", "1 2", "1 3", "2 0", "2 1", "2 2", "2 3", "3 0", "3 1", "3 2", "3 3" }

    Returns: 9

  54. {"1 1", "3 3", "4 4", "-1 1", "-2 2", "-3 3", "-4 4", "2 2", "-2 -2", "-3 -3", "1 0", "2 1", "3 2", "4 3", "-1 -1" }

    Returns: 12

  55. {"-8 -8", "8 -6", "8 12", "0 3", "-6 5", "3 11", "-3 1", "4 0", "3 7", "-9 10", "-3 -3", "1 -3", "-5 -5", "6 -4", "-20 10" }

    Returns: 15

  56. {"1 1", "2 1", "2 -2", "-1 -2", "-1 5", "0 5", "0 1", "0 2", "0 3", "0 4" }

    Returns: 9

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: