TopCoder problem "PointsOnACircle" used in SRM 382 (Division I Level Two)

Problem Statement


Two sets of points on a circle, A and B, are called similar if it is possible to rotate set B so that it coincides with set A.

You are given several points on a circle. You must color some of the points red and some of the points blue. (You can not color a point both red and blue.) The set of red points must be similar to the set of blue points.

You will be given the points as a String[] points. Concatenate all the elements of points to get a space separated list of points. Each point is a single integer representing its polar angle in degrees. Return the maximal number of points you can color.



Method signature:int color(String[] points)
(be sure your method is public)


-For a circle centered at O = (0, 0), the polar angle for a point P is the angle between lines OX and OP in the counterclockwise direction, where X is a point on the positive x-axis.


-points will contain between 1 and 50 elements, inclusive.
-Each element of points will contain between 1 and 50 characters, inclusive.
-Each element of points will contain only digits ('0'-'9') and spaces.
-When concatenated, the elements of points will form a single space-separated list of integers without leading or trailing spaces.
-Each integer in the list will be between 0 and 359, inclusive, with no extra leading zeros.
-All numbers in the list will be distinct.


{"0 10 15 25 40 50 60"}
Returns: 6
For example, you can color points 0, 15 and 40 red, and points 10, 25 and 50 blue.
Returns: 0
When there is only one point, you cannot create two separate sets of colored points.
{"0 1 3 7 15 31 63 127"}
Returns: 2
{"1","2"," ","3","4"}
Returns: 2

Problem url:

Problem stats url:




PabloGilberto , Olexiy , Jan_Kuipers , marek.cygan , ivan_metelsky

Problem categories:

Greedy, Search, Sorting