Statistics

Problem Statement for "SquareFind"

Problem Statement

Given a list of points you are to determine how many different squares can be made using these points as corners. The squares can be rotated (they need not be parallel to the axes) and points may be reused. A square is a polygon with 4 sides of equal length. Opposite sides are parallel, adjacent sides are perpendicular. All squares found must have a positive area ({(0,0),(0,0),(0,0),(0,0)} is not a square).

Create a class SquareFind that contains the method numSquares, which takes a int[] xs, and a int[] ys, and returns an int representing how many squares can be made.

Definition

Class:
SquareFind
Method:
numSquares
Parameters:
int[], int[]
Returns:
int
Method signature:
int numSquares(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 have the same number of elements.
  • xs will have between 1 and 50 elements, inclusive.
  • The elements of xs will be between -10000 and 10000, inclusive.
  • The elements of ys will be between -10000 and 10000, inclusive.
  • There will be NO repeated points.

Examples

  1. {0,0,2,2}

    {0,2,0,2}

    Returns: 1

    The following picture describes the points: . . X X . ......X.X..... . . . . As can be seen the 4 points make a single square.

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

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

    Returns: 6

    X X X . X . . X X X X X . . ......X.X.X... .........X.... . . . . . . . . The above left picture shows the points. As can be seen there are 5 squares aligned with the axes. Namely, the 4 small ones and the 1 large one. The harder to see square has been redrawn in the right picture above and is not aligned with the axes. Excuse the proportions due to the "text art".

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

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

    Returns: 2

    . . .X X . X ......X....... . X X. . . There are two squares not aligned with the axes. 1) A larger one on the left ((-2,1),(-1,-2),(2,-1),(1,2)) 2) A smaller on the right ((0,0),(1,2),(2,-1),(3,1))

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

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

    Returns: 50

  5. {0,0,0,4,4,4,-4,-4,-4}

    {4,-4,0,0,-4,4,4,0,-4}

    Returns: 6

  6. {1}

    {1}

    Returns: 0

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

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

    Returns: 175

  8. {-10000,-7500,-5000,-10000,-7500,-5000,-10000,-7500,-5000}

    {-10000,-10000,-10000,-7500,-7500,-7500,-5000,-5000,-5000}

    Returns: 6

  9. {-10000,-10000,-10000,0,0,0,10000,10000,10000}

    {-10000,0,10000,-10000,0,10000,-10000,0,10000}

    Returns: 6

  10. {0}

    {0}

    Returns: 0

  11. {0,2,2,4}

    {2,2,0,0}

    Returns: 0

  12. {0,1,2,3,4,5,6,7,1,2,3,4,5,6,7,8,2,3,4,5,6,7,8,9,3,4,5,6,7,8,9,10,4,5,6,7,8,9,10,11,5,6,7,8,9,10,11,12,99,100}

    {0,-1,-2,-3,-4,-5,-6,-7,1,0,-1,-2,-3,-4,-5,-6,2,1,0,-1,-2,-3,-4,-5,3,2,1,0,-1,-2,-3,-4,4,3,2,1,0,-1,-2,-3,5,4,3,2,1,0,-1,-2,99,100}

    Returns: 175

  13. {-10000,-6666,-3333,0,3333,6666,10000,-10000,-6666,-3333,0,3333,6666,10000,-10000,-6666,-3333,0,3333,6666,10000,-10000,-6666,-3333,0,3333,6666,10000,-10000,-6666,-3333,0,3333,6666,10000,-10000,-6666,-3333,0,3333,6666,10000,-10000,-6666,-3333,0,3333,6666,10000}

    {10000,10000,10000,10000,10000,10000,10000,6666,6666,6666,6666,6666,6666,6666,3333,3333,3333,3333,3333,3333,3333,0,0,0,0,0,0,0,-3333,-3333,-3333,-3333,-3333,-3333,-3333,-6666,-6666,-6666,-6666,-6666,-6666,-6666,-10000,-10000,-10000,-10000,-10000,-10000,-10000}

    Returns: 76

  14. {0,3,5,8}

    {0,4,0,4}

    Returns: 0

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

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

    Returns: 12

  16. {0,8,16,32,64,128,256,258,230,1000,-1000,-2000,-3000,-3500,0,8,16,32,64,128,256,258,230,1000,-1000,-2000,-3000,-3500,0,8,16,32,64,128,256,258,230,1000,-1000,-2000}

    {0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,2,2,2,2,2,2,2,2,2,2,2,2,2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2,-2}

    Returns: 2

  17. {0,8,0,8}

    {0,4,4,0}

    Returns: 0

  18. {3,0,-3,0}

    {0,1,0,-1}

    Returns: 0

  19. {0,10}

    {10,0}

    Returns: 0

  20. {0,0,0,4,4,4,-4,-4,-4}

    {4,-4,0,0,-4,4,4,0,-4}

    Returns: 6

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

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

    Returns: 50

  22. {0,5,8,3}

    {0,0,4,4}

    Returns: 0

  23. {-1,0,0,1}

    {0,2,-2,0}

    Returns: 0

  24. {2,0,4,2}

    {0,1,1,2}

    Returns: 0

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

    {9,8,7,6,5,9,8,7,6,5,9,8,7,6,5,9,8,7,6,5,9,8,7,6,5}

    Returns: 50

  26. {0,2,4,0,2,4,0,2,4}

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

    Returns: 6

  27. {0,4,5,9}

    {0,3,0,3}

    Returns: 0

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

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

    Returns: 50

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

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

    Returns: 1

  30. {0,0,0,4,4,4,-4,-4,-4}

    {4,-4,0,0,-4,4,4,0,-4}

    Returns: 6

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

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

    Returns: 50

  32. {-10000,10000,-9999,9999}

    {-10000,10000,9999,-9999}

    Returns: 0

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

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

    Returns: 3

  34. {1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10,1,2,3,4,5,6,7,8,9,10}

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

    Returns: 150

  35. {0,3,6,3}

    {0,2,0,-2}

    Returns: 0

  36. {0,4,0,4}

    {0,2,2,0}

    Returns: 0

  37. {0,0,-1,1}

    {2,-2,0,0}

    Returns: 0

  38. {0,3,0,-3}

    {4,0,-4,0}

    Returns: 0

  39. {0,0,0,0,0,0,0,0}

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

    Returns: 0

  40. {0,1,1,2}

    {1,0,2,1}

    Returns: 1

  41. {0,2,0,-2,6,7,8,6,7,8,6,7,8}

    {0,1,2,1,6,6,6,7,7,7,8,8,8}

    Returns: 6

  42. {0,8,0,8}

    {0,4,4,0}

    Returns: 0

  43. {0,0,0,4,4,4,-4,-4,-4}

    {4,-4,0,0,-4,4,4,0,-4}

    Returns: 6

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: