Connection Status:
Competition Arena > PointsOnACircle

PointsOnACircle

SRM 382 · 2007-12-11 · by andrewzta

SRM 382 · 2007-12-11 · by andrewzta · Greedy, Search, Sorting
Class Name: PointsOnACircle
Return Type: int
Method Name: color
Arg Types: (vector<string>)
Problem Statement

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.

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)
{"0 180"}
Returns: 2
4)
{"0 1 2 180 181 182"}
Returns: 6

Submissions are judged against all 135 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PointsOnACircle with a public method int color(vector<string> points) · 135 test cases · 2 s / 256 MB per case

Submitting as anonymous