Statistics

Problem Statement for "LineDraw"

Problem Statement

Given a plane containing points you are going to play connect the points. You will draw 2 separate straight lines. The lines may cross. Return how many points are not hit by either of your lines. You must pick the lines so that the return value is minimized. Note, a line extends infinitely in either direction. See examples for further clarification.

Create a class LineDraw that contains the method numPoints, which takes a int[] xs and an int[] ys representing the points in the plane, and returns an int that is the minimal amount of points not hit by either of your lines.

Definition

Class:
LineDraw
Method:
numPoints
Parameters:
int[], int[]
Returns:
int
Method signature:
int numPoints(int[] xs, int[] ys)
(be sure your method is public)

Notes

  • Point K will have x-coordinate xs[K] and y-coordinate ys[K].

Constraints

  • xs and ys will contain the same number of elements.
  • xs and ys will contain between 0 and 25 elements, inclusive.
  • The elements of xs will be between -20000 and 20000, inclusive.
  • The elements of ys will be between -20000 and 20000, inclusive.
  • There will be no repeated points.

Examples

  1. {0,0,0,1,1,1,2,2,2}

    {0,1,2,0,1,2,0,1,2}

    Returns: 3

  2. {0,0,0}

    {1,2,3}

    Returns: 0

  3. {1,2,3}

    {0,0,0}

    Returns: 0

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

    {0,0,1,0,2}

    Returns: 0

  5. {-1000,0,1000,-1000,0,1000,-1000,0,1000}

    {1000,1000,1000,0,0,0,-1000,-1000,-1000}

    Returns: 3

  6. {0,0,0,2,2,2,4,4,4}

    {0,2,4,0,2,4,0,2,4}

    Returns: 3

  7. {-2,0,0,2,2}

    {0,0,2,0,4}

    Returns: 0

  8. {0,2,4,0,2,4,0,2,4,-2}

    {0,0,0,2,2,2,4,4,4,6}

    Returns: 4

  9. {0,2,4,0,2,4,0,2,4,-2,6}

    {0,0,0,2,2,2,4,4,4,6,-2}

    Returns: 4

  10. {-20000,0,20000,-20000,0,20000,-20000,0,20000}

    {20000,20000,20000,0,0,0,-20000,-20000,-20000}

    Returns: 3

  11. {-20000,0,20000,-20000,0,20000}

    {20000,20000,19999,-19999,-20000,-20000}

    Returns: 2

  12. {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24}

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24}

    Returns: 0

  13. {4,4,4,4,4,4,4,4,4}

    {9,10,-23,-12,14,0,100,-100,-1000}

    Returns: 0

  14. {1,1,1,1,1,1,1,1,1}

    {0,1,2,3,4,5,6,7,8}

    Returns: 0

  15. {1}

    {2}

    Returns: 0

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

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

    Returns: 0

  17. {0,0,0,0,0,0,0,0,0,0,22,22,22,22,22,22,22,22}

    {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}

    Returns: 0

  18. {1,2}

    {2,3}

    Returns: 0

  19. {-20000,20000,-19999,-19998,0}

    {-20000,19999,-19999,-19998,0}

    Returns: 0

  20. {0,1,0}

    {0,0,1}

    Returns: 0

  21. {}

    {}

    Returns: 0

  22. {-20000,20000,20000,0,0}

    {-20000,20000,19999,1,2}

    Returns: 1

  23. {0}

    {0}

    Returns: 0

  24. {}

    {}

    Returns: 0

  25. {0}

    {0}

    Returns: 0

  26. {3,3,3,23,23,23,1234}

    {4,238,23,127,23,432,2376}

    Returns: 1

  27. {0,0,0,2,2,2,4,4,4}

    {0,2,4,0,2,4,0,2,4}

    Returns: 3

  28. {0,1,2}

    {0,1,2}

    Returns: 0

  29. {0,5,5,0}

    {0,0,5,5}

    Returns: 0

  30. {}

    {}

    Returns: 0

  31. {0,0,0,0,0}

    {0,1,2,3,4}

    Returns: 0

  32. {1}

    {1}

    Returns: 0

  33. {1}

    {2}

    Returns: 0

  34. {-15000,500,600,844,923,-145,-8724,8858,9685,-1273,500,-4857,-8887,2001,-2834,0,1,2,3,4,5,6,12,58,47}

    {5768,9867,-4958,-15867,6867,19058,9685,9875,-6857,-17684,9657,6857,5768,-2834,13875,0,1,2,3,4,5,8,9,4,0}

    Returns: 17

  35. {1,2,3,5,-1}

    {90,-10,-1,1,1}

    Returns: 1

  36. {0,1,2,3}

    {0,1,2,3}

    Returns: 0

  37. {1,1,2,3,1,1,1,1}

    {0,1,2,3,4,5,6,7}

    Returns: 0

  38. {1,2,3,4,5}

    {2,2,3,4,5}

    Returns: 0

  39. {1}

    {2}

    Returns: 0

  40. {0,1,1,2,2}

    {0,1,0,1,0}

    Returns: 0

  41. {1,1,1,1,1}

    {3,4,5,6,7}

    Returns: 0

  42. {1,9,81,5,-1000}

    {-98,-500,500,25,16}

    Returns: 1

  43. {1,2,3,4,5,6,7,8,9,0,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25}

    {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25}

    Returns: 0

  44. {0,0,0,2,4,4,4}

    {0,2,4,3,2,4,6}

    Returns: 1

  45. {999,-999,999,-999,0,1}

    {1000,1000,-1000,-1000,0,1}

    Returns: 1

  46. {1}

    {2}

    Returns: 0

  47. {}

    {}

    Returns: 0

  48. {1}

    {1}

    Returns: 0

  49. {}

    {}

    Returns: 0

  50. {1}

    {2}

    Returns: 0

  51. {0,0,0,1,1,2,2}

    {0,1,2,0,2,0,2}

    Returns: 1

  52. {1}

    {1}

    Returns: 0

  53. {0,100,200,300,400,500,-45,-90,-135,-180,8,2}

    {0,3,6,9,12,15,-8,-16,-24,-32,7,3}

    Returns: 2

  54. {1}

    {1}

    Returns: 0

  55. {1}

    {1}

    Returns: 0

  56. {0,2,4,0,2,4,0,2,4,-2}

    {0,0,-1,2,2,3,5,4,4,7}

    Returns: 4

  57. {}

    {}

    Returns: 0

  58. {0,1,2,3,4}

    {1,0,1,0,1}

    Returns: 0

  59. {}

    {}

    Returns: 0

  60. {}

    {}

    Returns: 0

  61. {0,0,0,0,0,1,1,1,1,2}

    {3,4,5,6,7,3,4,5,6,3}

    Returns: 1

  62. {0,0,0,2,2,2,4,4,4}

    {0,2,4,0,2,4,0,2,4}

    Returns: 3

    This would look like ('.'s represent points, 'X's represent the axes): . . . X . . . X XXXXXX.X.X.XXX X X X X Two lines must be drawn so that the least number of points are not on either line. Here is one possible pair of lines that satisfy the requirement: -------------- X -------------- X XXXXXX.X.X.XXX X X X X There are other possible pairs of lines that produce the same result. There are 3 points through which lines do not pass so your method returns 3.

  63. {-2,0,0,2,2}

    {0,0,2,0,4}

    Returns: 0

    This would look like: X . X . X XXXX.X.X.XXXXX X X X X Two lines must be drawn so that the least number of points are not on either line. This would look like: X / X/ / /X -------------- / X / X / X / X There are 0 points through which lines do not pass so your method returns 0.

  64. {1}

    {2}

    Returns: 0

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

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

    Returns: 0

  66. {0,2,4,0,2,4,0,2,4,-2}

    {0,0,0,2,2,2,4,4,4,6}

    Returns: 4

  67. {-20000,0,20000,-20000,0,20000,-20000,0,20000}

    {20000,20000,20000,0,0,0,-20000,-20000,-20000}

    Returns: 3

  68. {1,1,1,1,1,1,1,1}

    {0,1,2,3,4,5,6,7}

    Returns: 0

  69. {1,2}

    {2,3}

    Returns: 0

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: