Get Time

   Problem Statement  

 Problem Statement for DrawingPointsDivOne

Problem Statement

    This problem statement contains images. It may not display properly outside the applet.

Once upon a time, Little Wojtek had drawn a number of points with integer coordinates onto a sheet of paper. Then he made zero or more steps. Each step looked as follows: Let's call all the points on Wojtek's paper old points. For every four old points that formed the vertices of a 1x1 square, Wojtek would draw a point in the middle of that square. Once he had drawn all such new points, he took an eraser and erased all the old points.

An example is shown in the picture below. On the left is Wojtek's original paper. In the middle is the same paper with the new points filled in. (For clarity, the old points are black and the new ones are red.) On the right is the paper after the old points were erased.


He has been playing for a while when he was called downstairs to dinner. He looked at the paper with a surprised face and wondered how many steps he had made.

You are given two int[]s x, y of some equal length n. They describe all of the points that were drawn by Wojtek in the last step of his play. More precisely, you may assume that there are real numbers (not necessarily integers) dy and dx such that the following holds:

  • For each i between 0 and n-1, there is a point at coordinates (dx+x[i], dy+y[i]).
  • There are no other points anywhere on the paper, only those that follow from the previous statement.

Return the maximum number of steps Wojtek could have made. If there is no maximum (that is, if the number of steps can be arbitrarily large), return -1 instead.



Parameters:int[], int[]
Method signature:int maxSteps(int[] x, int[] y)
(be sure your method is public)


-Note that the points drawn by Wojtek in the last step of his play could have non-integer coordinates.
-The paper used by Wojtek could have been arbitrarily large. In other words, ignore the paper size, it does not limit the number of steps in any way.


-x will contain between 1 and 50 elements, inclusive.
-x and y will contain the same number of elements.
-Each element of x will be between -70 and 70, inclusive.
-Each element of y will be between -70 and 70, inclusive.
-No two points described by x and y will be the same.


{0, 3}
{0, 0}
Returns: 1
An example scenario:

  • Wojtek draws the initial points at locations (100, 100), (100, 101), (101, 100), (101, 101), (103, 100), (104, 100), (103, 101), (104, 101), (315, 714).
  • In the first and only step, Wojtek draws points at locations (100.5, 100.5) and (103.5, 100.5). These locations correspond to x and y in this test case.
Returns: 0
Returns: -1
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)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 560 Round 1 - Division I, Level Two