PROBLEM STATEMENT
Let us consider a square piece of a plane with opposing corners at {0,0} and
{100,100}. Let us take four points on this plane with integer coordinates. The
convex hull (see definition at end of statement) of those four points
represents a quadrilateral (which could be degenerated to a triangle, a segment
or a point). The four points will be given as an int[]
{x1,y1,x2,y2,x3,y3,x4,y4}, where x1 represents the x-coordinate of the first
point, y1 represents the y-coordinate of the first point, etc. To simplify your
task, TopCoder will check that all four points are distinct and they do not lie
on the same line. That means that the convex hull of the input points can't
degenerate to a point or a segment.
Your task is, given a set of coordinates of four points on a plane return the
shape of its convex hull. The return String should be one of the following
(quotes included for clarity): "TRIANGLE", "SQUARE", "RECTANGLE", "RHOMBUS",
"PARALLELOGRAM", "TRAPEZOID", "QUADRILATERAL".
NOTE
- Often, a square is considered to be a type of a rectangle. You should return
"SQUARE" if it is a square, or "RECTANGLE" if it is a rectangle but not a
square. In general, if you can fit the given four points into several
definitions return the leftmost one (closest to the beginning in the list
above) which is correct. For example, four points that form a rhombus can be
considered as a particular case of a parallelogram, you should return
"RHOMBUS", as the "RHOMBUS" is the leftmost definition that fits. For your
convenience, definitions are given below the examples.
- 3 out of the 4 points may be colinear
DEFINITION
Class: Quadrilateral
Method: shape
Parameters: int[]
Returns: String
Method signature (be sure your method is public): String shape(int[] points);
TopCoder will ensure the validity of the inputs. Inputs are valid if all of the
following criteria are met:
- points has exactly 8 elements
- each element of points is between 0 and 100 inclusive
- the four points on the plane represented by points are all distinct
- the four points on the plane represented by points don't all lie on the same
line
EXAMPLES
The example pictures are oriented in such a way that the left-upper corner of
our plane piece has coordinates {0,0}, the right-upper corner - {0,100}, the
left-bottom - {100,0} the right-bottom - {100,100}
1. points = {0,1,1,2,2,1,1,0} represent a square:
.X.....
X.X....
.X.....
.......
return "SQUARE"
2. points = {2,0,0,1,4,0,0,2}:
..X.X...
X.......
X.......
return "TRAPEZOID"
3. points = {0,0,3,0,0,2,1,1}:
X..X..
.X....
X.....
return "TRIANGLE"
4. points = {0,2,0,0,1,2,1,0}:
X.X.
X.X.
....
return "RECTANGLE"
5. points = {0,10,0,30,7,0,7,20} return "PARALLELOGRAM"
6. points = {0,2,3,0,5,2,3,4} return "QUADRILATERAL"
7. points = {0,0,0,5,3,4,3,9} return "RHOMBUS"
8. points = {56,46,57,46,58,46,56,47} return "TRIANGLE"
DEFINITIONS
1. CONVEX HULL of 4 points is the intersection of all convex polygons
containing those points. A polygon is not convex if there exist some two points
inside the polygon, such that the line segment connecting these points doesn't
lie completely inside the polygon.
Here are two suggestions to help you visualize the convex hull. 1. Take all the
line segments connecting all the four points. You will get a figure with some
line segments inside. The border of this figure is the convex hull of the four
points. 2. You can picture the convex hull of four points if you imagine these
points as posts on the ground and put a tight rubber band around all posts. The
rubber band will become the border of the convex hull of the four posts.
2. SQUARE is a quadrilateral with sides of equal length and all angles equal to
90 degrees.
3. RECTANGLE is a quadrilateral with all angles equal to 90 degrees.
4. RHOMBUS is a quadrilateral with all sides of equal length.
5. PARALLELOGRAM is a quadrilateral which has two pairs of opposite sides
parallel to each other.
6. TRAPEZOID is a quadrilateral which has a pair of sides parallel to each other.