SquarePoints

SRM 192 · 2004-04-27 · by lbackstrom

SRM 192 · 2004-04-27 · by lbackstrom · Geometry

Show categories

Class Name: SquarePoints

Return Type: String

Method Name: determine

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

Problem Statement

This problem contains images which will not display correctly for plugin users. Please use the applet to view the problem statement and examples.

Given a set of two-dimensional points with integer coordinates, determine if they uniquely determine a square. In other words, determine if there is exactly one square that can be constructed so that each specified point is exactly on an edge or vertex of the square. Return "consistent" if exactly one such square exists, "inconsistent" if no such square exists, and return "ambiguous" if more than one such square is possible. To simplify the problem a bit, input will contain at least five points. The coordinates of the points are specified in two int[]s, x and y. The i'th point is specified by (x[i],y[i]).

For example:

x={0,0,2,3,5,5,3,2}
y={2,3,0,0,3,2,5,5}

Returns "ambiguous" since two squares can be constructed such that each passes through all eight points, as shown in the figure.

Notes

The possible squares may be at any orientation(s).

Constraints

x will have between 5 and 50 elements inclusive.
y will have between 5 and 50 elements inclusive.
x and y will have the same number of elements.
Each element of x and y will be between -1000 and 1000 inclusive.
Each point (x[i],y[i]) must be distinct from all the other points.

Examples

{0,0,2,3,5,5,3,2}
{2,3,0,0,3,2,5,5}
Returns: "ambiguous"

The example from above.

{0,0,10,10,5}
{0,10,0,10,0}
Returns: "consistent"

Only one way here.

{1,2,3,4,5,6,7,8,9,0,-10}
{0,2,3,4,5,6,7,8,9,100,-3}
Returns: "inconsistent"

{1,2,3,4,5,6,7,8,9,11,12}
{1,2,3,4,5,6,7,8,9,12,11}
Returns: "inconsistent"

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

{0,0,10,10,4}
{0,10,0,10,5}
Returns: "inconsistent"

No way to make a square with all the points here.

{1,1,1,1,1,1,1,1,1,1,1,1,1,2,3,4,5,6,7,8,9,10,11,12,13,
13,13,13,13,13,13,13,13,13,13,13,13,12,11,10,9,8,7,6,5,4,3,2}
{1,2,3,4,5,6,7,8,9,10,11,12,13,13,13,13,13,13,13,13,13,13,13,13,13,
12,11,10,9,8,7,6,5,4,3,2,1,1,1,1,1,1,1,1,1,1,1,1}
Returns: "consistent"

This is an extremely well determined square.

11)

{ 0,4,8,-5,-1,3}
{ 0,3,6,15,18,21}
Returns: "consistent"

Exactly one square fits here.

12)

{ 0,4,8,-5,-1,3,16}
{ 0,3,6,15,18,21,12}
Returns: "inconsistent"

No square is possible.

13)

{0,4,8,-5,-1}
{0,3,6,15,18}
Returns: "ambiguous"

More than one square is possible. Three of them are shown here.

27)

{998,-1000,-998,1000,999}
{1000,998,-1000,-998,0}
Returns: "inconsistent"

Almost a square, but not quite.

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

Coding Area

Language: C++17 · define a public class SquarePoints with a public method string determine(vector<int> x, vector<int> y) · 43 test cases · 2 s / 256 MB per case