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.

 

Definition

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

Notes

-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.
 

Constraints

-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.
 

Examples

0)
    
{"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.
1)
    
{"1"}
Returns: 0
When there is only one point, you cannot create two separate sets of colored points.
2)
    
{"0 1 3 7 15 31 63 127"}
Returns: 2
3)
    
{"1","2"," ","3","4"}
Returns: 2

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8238

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10805&pm=8238

Writer:

andrewzta

Testers:

PabloGilberto , Olexiy , Jan_Kuipers , marek.cygan , ivan_metelsky

Problem categories:

Greedy, Search, Sorting