Statistics

Problem Statement for "SquareCovering"

Problem Statement

A square covers a point on a plane if this point lies on the border of this square.

You will be given int[]s px and py, with the i-th elements of px and py representing x and y coordinates of a point on a plane. Find the smallest square with its sides parallel to coordinate axes, which can cover all points from the input and return the length of its side. If no such square exists, return -1.

Definition

Class:
SquareCovering
Method:
getMinimalSide
Parameters:
int[], int[]
Returns:
int
Method signature:
int getMinimalSide(int[] px, int[] py)
(be sure your method is public)

Constraints

  • px will contain between 2 and 50 elements, inclusive.
  • px and py will contain the same number of elements.
  • All elements of px and py will be between -1000 and 1000, inclusive.
  • All points specified by px and py will be different.

Examples

  1. {0,1}

    {0,1}

    Returns: 1

    Both points can be covered with a square with vertices (0,0), (1,0), (1, 1) and (0, 1).

  2. {0,1,2}

    {0,1,2}

    Returns: -1

    These points can not be covered by a square.

  3. {1,-3, 2}

    {1, 0, -4}

    Returns: 5

  4. {-10, 0, 3, -1}

    {0, -1, 3, 4}

    Returns: -1

    These points can be covered by a rectangle, but not by a square.

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

    {1000,1000,1000,1000,1000,1000,1000,1000,1000,1000}

    Returns: 9

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

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

    Returns: 4

  7. {1000,-1000,-1000}

    {1000,-1000,1000}

    Returns: 2000

  8. {1000,-1000,-1000,1000}

    {1000,-1000,1000,-1000}

    Returns: 2000

  9. {-777,-777,-577}

    {100,-100,0}

    Returns: 200

  10. {235,245,240}

    {620,615,625}

    Returns: 10

  11. {63,163,153,70}

    {10,90,0,100}

    Returns: 100

  12. {-2,-2,-2,5,100,120,201,202,203}

    {1,100,120,-2,-2,-2,500,500,500}

    Returns: 502

  13. {-1000,1000,0}

    {0,0,-1000}

    Returns: 2000

  14. {0,0,0,-199,-199}

    {0,-200,-100,0,-200}

    Returns: 200

  15. {111,111,500}

    {10,9,10}

    Returns: 389

  16. {63,164,153,70}

    {10,90,0,100}

    Returns: -1

  17. {-773,-773,139,-773,268,-190,138,-114,-773,-773,268,-24,-773,-536,-590,54,-773,-410,-204,-711,268,-773,-654,-773,-773,268,-386,268,81,-465,-485,-69,-265,-773,268,268,-355,268,-773,-655,-773,-773,-773,-773,-113,-446,-285,-768,268,-302}

    {-13,-410,-426,69,-69,615,615,-426,-337,350,-134,-426,536,615,-426,-426,233,615,-426,615,575,127,615,113,-66,-187,615,11,-426,615,-426,-426,-426,-72,-166,-22,-426,1,447,615,-426,372,-41,-154,615,615,-426,-426,239,615}

    Returns: 1041

  18. {253,253,253,-846,-517,253,253,-756,253,-279,-672,206,-796,253,-716,-355,-509,253,253,253,253,253,-100,84,253,-846,-291,13,-846,-846,-105,-696,-810,-826,-846,-846,-846,253,253,-408,-846,-379,-846,-846,-625,-829,253,253,105,-846}

    {-886,-606,-847,-620,-992,-819,-980,-992,44,107,107,107,-992,-168,-992,107,107,-805,-509,-883,-34,-4,-992,-992,-424,-301,-992,-992,-255,-9,107,-992,107,-992,-71,-893,-708,-658,-93,-992,-504,107,-399,-509,107,-992,-278,24,107,-143}

    Returns: 1099

  19. {615,-244,72,615,615,615,54,-200,-410,-273,-426,615,-329,460,-350,615,-177,90,461,-311,615,615,615,126,29,615,-63,615,-426,374,-426,-426,-426,455,51,336,457,615,615,-426,-426,-344,-168,-426,477,615,614,615,615,56}

    {684,-720,-720,217,355,-229,711,711,711,-720,206,-620,-720,711,711,576,711,711,711,-720,-352,-169,420,711,-720,683,711,58,-549,-720,-686,-370,448,-720,-720,-720,-720,-36,447,618,-336,-720,711,215,-720,-662,-720,69,323,711}

    Returns: -1

  20. {-760,493,-339,493,-427,-35,-760,-412,-760,-527,493,493,-760,246,-407,55,415,-444,-760,-634,-760,-760,364,85,493,-760,493,335,493,493,-760,-80,-760,-225,493,493,-639,-207,-507,-760,493,-760,493,493,-760,-760,493,-513,493,493}

    {-339,-246,639,55,639,-604,-284,-604,532,-604,290,429,626,-604,-604,-604,-604,639,-289,-604,-453,-350,-604,639,-366,-432,294,-604,119,504,149,639,-582,639,400,477,639,-604,-604,-278,-483,472,306,413,-375,-524,-1,-604,200,40}

    Returns: -1

  21. {-1, 0, 0}

    {0, 0, -1}

    Returns: 1

  22. {-1, 0, 0}

    {0, 1, 0}

    Returns: 1

  23. {-1000, -1000}

    {-1000, 1000}

    Returns: 2000

  24. {1000, 1000}

    {-1000, 1000}

    Returns: 2000

  25. {-1000, 1000}

    {-1000, -1000}

    Returns: 2000

  26. {-1000, 1000}

    {1000, 1000}

    Returns: 2000

  27. {1, 1, 1, 2 }

    {1, 2, 3, 1 }

    Returns: 2

  28. {0, 10 }

    {0, 1 }

    Returns: 10

  29. {100, 200, 100 }

    {1, 2, 3 }

    Returns: 100

  30. {2, 2, 5, 5 }

    {4, -1, 3, 0 }

    Returns: 5

  31. {5, 6, 5, 6 }

    {0, 0, 20, 20 }

    Returns: 20

  32. {0, 0, 0, 0, 0, 10, 10, 10, 10, 10 }

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

    Returns: 10

  33. {-959, -367, 76, -585, 965, 132, -814, 183, 920, -517, 965, -497, 965, 965, -142, 256, 805, -517, -941, -992, -446, -241, 460, 470, 751, 965, -506, -339, 965, -653, -638, 168, 399, 965, 965, 965, 965, 965, 965, 965, -41, 394, 551, 735, -980, -404, 965, 965, -27, 558 }

    {966, -996, -996, 966, -622, 966, 966, 966, 966, -996, 948, -996, 862, 136, -996, 966, -996, 966, -996, -996, 966, -996, -996, -996, 966, -929, -996, 966, 562, 966, 966, 966, -996, -541, 501, 859, -235, 929, 460, -55, -996, -996, -996, -996, 966, -996, -165, 790, -996, 966 }

    Returns: 1962

  34. {0, 0, 0, 0, 0, 10, 10, 10, 10, 10, 5 }

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

    Returns: 10

  35. {969, 969, -998, 969, -998, -884, -998, 969, -998, 115, 969, -499, -998, 969, -998, 969, 969, -998, -911, -998, -998, -998, 969, -998, -998, -338, 293, 72, -998, -454, -998, -649, -998, -463, 817, 969, -998, 969, -998, -998, 969, 521, -998, 969, -998, 969, 60, 969, 65, 969 }

    {-881, -189, 142, 190, -475, 972, 273, -430, 504, 972, 237, 972, 232, 482, 67, -863, 247, 467, 972, -190, 555, 912, -22, -801, -288, 972, 972, 972, -927, 972, -852, 972, -205, 972, 972, -522, -496, 45, 116, 382, -913, 972, 779, -892, 767, -940, 972, 32, 972, 246 }

    Returns: 1967

  36. {0, 1, 3 }

    {1, 2, 0 }

    Returns: 3

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: