CentersOfSymmetry

SRM 394 · 2008-03-22 · by Xixas

SRM 394 · 2008-03-22 · by Xixas · Geometry, Math

Show categories

Class Name: CentersOfSymmetry

Return Type: int

Method Name: lineConfigurations

Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>)

Problem Statement

We have n straight lines drawn in the Cartesian plane each described by two distinct points (x1[i], y1[i]) and (x2[i], y2[i]) lying on it. A center of symmetry is such a point that under a symmetry centered at this point the given configuration of lines goes into itself (i.e., the image of every given line under this symmetry is again one of the given lines). Return the number of centers of symmetry that the given system of lines has. Return -1 if there are infinitely many centers of symmetry.

Notes

A symmetry centered at point X works as follows. The image of a point A is such a point B that X is the midpoint of the line segment AB (note that if A = X, then also B = X). The image of a line is the union of images of all points on this line.

Constraints

x1 will contain between 1 and 50 elements, inclusive.
x1, y1, x2, y2 will all contain the same number of elements.
All the elements of x1, y1, x2 and y2 will be between -50 and 50, inclusive.
For each i either x1[i] and x2[i] or y1[i] and y2[i] will be distinct (i.e., two points defining a line will be distinct).
All the lines defined by (x1[i], y1[i]) and (x2[i], y2[i]) will be distinct.

Examples

{0, 0}
{0, 0}
{1, -1}
{1, 1}
Returns: 1

A configuration of two intersecting lines has a single center of symmetry - their intersection point.

{0, 0, 0, 0, 0, 0, 0, 0, 0}
{0, 0, 0, 0, 0, 0, 0, 0, 0}
{1, 1, 1, 1, 1, 1, 1, 1, 1}
{1, 2, 3, 4, 5, 6, 7, 8, 9}
Returns: 1

All the lines pass through the origin.

{0, 1, 2}
{0, 1, -1}
{1, 2, 0}
{1, -1, 0}
Returns: 0

{-10, 10}
{10, -10}
{-10, 10}
{-10, 10}
Returns: -1

Two parallel lines produce infinitely many centers of symmetry.

{-50, -50, -50, -50}
{-50, -49, -48, -46}
{50, 49, 48, 46}
{50, 50, 50, 50}
Returns: 0

4 parallel lines with no centers of symmetry.

{7}
{11}
{10}
{-7}
Returns: -1

A single line.

{0,0,0,0}
{0,7,4,3}
{10,20,30,40}
{0,7,4,3}
Returns: -1

Next 4 don't delete

{2, -9, 1, 21, -15, 13, 6, -3, -3, 1, 0, 0, 12, 9, 29}
{13, -2, 5, -27, -4, 2, 3, 10, 0, 11, 0, 3, -5, 8, -19}
{5, -5, 2, 24, -11, 10, 3, -5, -5, 3, 8, 2, 0, -11, 32}
{1, 0, 5, -31, -2, 3, 6, 10, 0, 7, 10, 4, 10, -4, -23}
Returns: 1

next 11 are random configurations with a center of symmetry

20)

{-24, 45, 28, -15, -50, 16}
{-42, 39, -13, 29, 2, -2}
{5, -33, -16, 40, -4, -26}
{35, 9, 37, 28, -33, 46}
Returns: 0

next 19 are random lines

39)

{-27, -24, -21, -36, -43, -42, -26, -26}
{20, 16, 23, 24, 35, 32, 22, 24}
{-31, -28, -25, -24, -35, -38, -30, -34}
{23, 19, 26, 15, 29, 29, 25, 30}
Returns: 0

next 9 are random parallel

47)

{-13, 32, 28, 26, -26, 31, 37}
{-26, 40, 44, 36, -9, -45, 11}
{-15, 34, 26, 28, -30, 33, 39}
{-26, 40, 44, 36, -9, -45, 11}
Returns: 0

next 2 are random parallel horizontal

49)

{-6, 40, 36, 34, -20, 45}
{-33, 32, 36, 28, -15, 3}
{-6, 40, 36, 34, -20, 45}
{-35, 34, 34, 30, -19, 5}
Returns: 0

next 4 are random parallel vertical

53)

{16, 1, 3, 11, 5, -10, -5}
{-15, 39, 2, 9, 5, 28, -16}
{16, 1, 3, 11, 5, -10, -5}
{29, -33, -4, 28, 35, -50, 37}
Returns: -1

next 8 are random vertical parallel symmetrically spaced

61)

{-20, -24, 1, 19, 50, 4, -17}
{-9, -2, -1, -1, 8, 1, -1}
{1, -3, -8, -2, 44, -2, -14}
{-2, 5, -4, -8, 6, -1, 0}
Returns: -1

next 3 are random symetrically spaced parallel

64)

{-15, 39, 2, 9, 5, 28, -16}
{16, 1, 3, 11, 5, -10, -5}
{29, -33, -4, 28, 35, -50, 37}
{16, 1, 3, 11, 5, -10, -5}
Returns: -1

next 8 are horizontal parallel symetrically spaced

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

Coding Area

Language: C++17 · define a public class CentersOfSymmetry with a public method int lineConfigurations(vector<int> x1, vector<int> y1, vector<int> x2, vector<int> y2) · 82 test cases · 2 s / 256 MB per case