O-Quadrilaterals
You are given four points in a plane. Find out which type of a quadrilateral is determined by these 4 points.
If several types of quadrilaterals are possible, provide only one name, chosen according to the following list of priorities:
Square
Rectangle
Rhombus
Rhomboid
Kite
Trapezoid
Convex - Convex quadrilateral which cannot be classified as one of those listed above.
Dart - Concave two pairs with equal neighboring sides (like a kite but concave)
Concave - Concave quadrilateral which cannot be classified as a dart.
None - Three or more points are collinear or two or more points are the same.
The first line contains an integer T, the number of test cases (T <= 10000).
In the next T lines there are eight integers in each line: Ax, Ay, Bx, By, Cx, Cy, Dx, Dy. All coordinates are between -10^9 and 10^9, inclusive. For quadrilaterals which match any of the types 1 to 9, the points of quadrilaterals will be ordered anticlockwise.
Input:
10
0 0 1 1 2 2 0 2
0 0 1 -1 2 0 1 1
0 0 1 -2 2 0 1 2
0 0 1 -1 2 0 1 2
0 0 1 1 2 0 1 2
2 0 3 2 0 3 0 0
0 0 1 1 3 0 1 2
3 2 0 2 0 0 3 0
0 0 1 1 1 3 0 4
0 0 6 2 4 3 -2 1
Output:
None
Square
Rhombus
Kite
Dart
Convex
Concave
Rectangle
Trapezoid
Rhomboid
Explanation: in the second test, the conditions for all types of convex quadrilaterals are matched. Since the square is the first in the priority list above, the correct answer is "Square".
There are five set of tests
Set 1 - first two types of quadrilaterals only, T = 20.
Set 2 - parallelograms only, T = 100.
Set 3 - convex types of quadrilaterals only, T = 500.
Set 4 - all types, T = 1000.
Set 5 - all types, T = 10000.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.