Statistics

Problem Statement for "TreeLine"

Problem Statement

A farmer has several trees planted, the locations of which are given in int[]s x and y, where (x[i], y[i]) indicates the location of the i-th tree. The farmer notices that some of them form straight lines with one another and wonders, what is the largest numver of trees that are perfectly colinear with each other?

Definition

Class:
TreeLine
Method:
longest
Parameters:
int[], int[]
Returns:
int
Method signature:
int longest(int[] x, int[] y)
(be sure your method is public)

Constraints

  • x will have between 1 and 50 elements, inclusive.
  • x and y will have the same number of elements.
  • Each element of x will be between 0 and 1000, inclusive.
  • Each element of y will be between 0 and 1000, inclusive.
  • No elements of x and y will refer to the same point.

Examples

  1. {0, 3, 6}

    {0, 3, 6}

    Returns: 3

    All three trees for a line.

  2. {0, 3, 6}

    {0, 3, 7}

    Returns: 2

    Notice the last tree is not in line with the first two.

  3. {0, 3, 6, 20, 12}

    {0, 3, 0, 20, 11}

    Returns: 3

    Trees 0, 1 and 3 line up, the other two do not.

  4. {0, 3, 6, 20, 12}

    {0, 3, 0, 19, 0}

    Returns: 3

  5. {1}

    {2}

    Returns: 1

  6. {893, 56, 231, 353, 954, 215, 829, 651, 524, 87, 552, 877, 258, 743, 625, 703, 892, 742, 738, 48, 810, 545, 563, 488, 405, 887, 140, 850, 15, 151, 983, 670, 35, 713, 536, 944, 840, 435, 973, 318, 303, 584, 860, 645, 398, 270, 39, 640, 763, 325}

    {425, 662, 58, 366, 791, 651, 795, 521, 789, 610, 48, 237, 466, 528, 793, 551, 886, 882, 942, 433, 530, 837, 441, 567, 150, 599, 518, 430, 777, 473, 479, 588, 619, 222, 915, 701, 251, 374, 79, 59, 926, 195, 76, 435, 148, 913, 788, 498, 270, 550}

    Returns: 2

  7. {46, 20, 9, 1, 49, 15, 8, 4, 10, 2, 49, 49, 33, 20, 13, 17, 6, 41, 30, 49, 25, 38, 36, 35, 4, 15, 7, 45, 3, 7, 21, 43, 37, 27, 36, 47, 20, 44, 49, 47, 34, 34, 32, 38, 36, 1, 18, 39, 17, 35}

    {45, 22, 9, 12, 2, 39, 12, 33, 44, 20, 8, 18, 36, 47, 0, 19, 12, 44, 28, 11, 2, 46, 37, 5, 26, 28, 19, 36, 47, 8, 2, 26, 37, 17, 42, 16, 2, 22, 43, 9, 14, 3, 34, 12, 24, 23, 8, 15, 33, 26}

    Returns: 5

  8. {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, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49}

    {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, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49}

    Returns: 50

  9. {21}

    {168}

    Returns: 1

  10. {705,776,274,490,522}

    {838,915,199,393,87}

    Returns: 2

  11. {366,953,734,700,583,534,728,992,786,614,196,280,831,246,839,966,218,573,965,463}

    {562,958,865,68,542,211,616,242,945,980,863,189,812,561,514,57,871,732,565,835}

    Returns: 2

  12. {257,338,974,466,12,648,118,666,259,143,482,599,434,398,53,967,851,537,62,46,662,933,441,73,793,23,837,754,339,159,972,576,289,950,77,409,144,913,993,882,296,204,380,320,711,974,355,475,657,328}

    {497,227,176,428,966,552,404,511,41,971,621,313,698,45,559,409,797,487,519,748,207,485,984,753,524,2,153,221,459,22,835,68,287,726,771,860,21,744,657,801,248,60,712,201,789,744,749,574,532,545}

    Returns: 2

  13. {68,82,345,481,464,552,505,925,732,494,48,807,374,72,959,954,779,223,244,197,901,828,64,629,125,248,156,853,560,263,309,667,556,20,368,938,315,989,889,986,988,881,213,630,636,368,337,962,904,799}

    {784,493,573,359,386,955,654,129,132,553,633,460,852,843,864,108,67,130,433,762,780,549,47,267,104,460,601,981,647,39,164,973,590,395,95,848,531,281,418,623,173,422,486,532,958,608,353,775,712,97}

    Returns: 2

  14. {948,980,819,371,684,947,478,688,60,772,988,254,862,212,477,56,261,924,490,458,866,175,691,692,52,439,314,948,471,202,556,971,497,21,598,934,717,149,384,456,354,192,707,959,822,21,523,61,313,692}

    {351,79,488,335,629,779,996,165,164,979,826,614,540,326,92,887,163,969,202,620,28,574,19,388,201,447,678,230,190,156,96,929,236,138,457,772,414,951,655,259,259,379,887,694,423,225,199,747,614,567}

    Returns: 2

  15. {2 }

    {2 }

    Returns: 1

  16. {0 }

    {1 }

    Returns: 1

  17. {0, 3, 6, 20, 12 }

    {0, 3, 0, 20, 11 }

    Returns: 3

  18. {4 }

    {2 }

    Returns: 1

  19. {0, 3, 6 }

    {0, 3, 7 }

    Returns: 2

  20. {1 }

    {2 }

    Returns: 1

  21. {1, 1, 1, 1 }

    {1, 2, 5, 7 }

    Returns: 4

  22. {1, 2 }

    {2, 4 }

    Returns: 2

  23. {1, 1, 1 }

    {1, 2, 3 }

    Returns: 3

  24. {1, 2, 3, 4 }

    {2, 4, 6, 8 }

    Returns: 4

  25. {1, 1, 1 }

    {1, 2, 4 }

    Returns: 3

  26. {1, 2, 3 }

    {0, 1, 2 }

    Returns: 3

  27. {1 }

    {1 }

    Returns: 1

  28. {0, 0 }

    {1, 2 }

    Returns: 2

  29. {0, 1, 2, 3 }

    {0, 2, 4, 6 }

    Returns: 4

  30. {1, 2, 3, 2, 1, 1, 1 }

    {1, 2, 3, 1, 2, 3, 10 }

    Returns: 4

  31. {2, 3 }

    {3, 4 }

    Returns: 2

  32. {0, 1, 2 }

    {0, 0, 0 }

    Returns: 3

  33. {1, 1, 1 }

    {1, 3, 6 }

    Returns: 3

  34. {1, 2, 3 }

    {2, 4, 6 }

    Returns: 3

  35. {1, 2, 3 }

    {1, 2, 3 }

    Returns: 3

  36. {0, 3, 6 }

    {0, 3, 6 }

    Returns: 3

  37. {4 }

    {1 }

    Returns: 1

  38. {0 }

    {0 }

    Returns: 1

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

    {10, 2, 3, 4, 5 }

    Returns: 4

  40. {1, 5 }

    {1, 8 }

    Returns: 2

  41. {1, 1, 2, 2 }

    {1, 2, 1, 2 }

    Returns: 2

  42. {0, 3, 6, 7, 8 }

    {0, 3, 6, 8, 9 }

    Returns: 3

  43. {10, 11, 12, 13 }

    {5, 4, 3, 2 }

    Returns: 4

  44. {1, 1, 1, 2, 3 }

    {2, 3, 4, 4, 6 }

    Returns: 3

  45. {1, 2, 2, 3, 4 }

    {1, 2, 1, 2, 3 }

    Returns: 3

  46. {1, 0 }

    {2, 0 }

    Returns: 2

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: