Submit | All submissions | Best solutions | Back to list |

## HS12QUAD - 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.

### Input

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.

### Output

For every test, write which kind of quadrilateral is determined by these four points.

### Example

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 1Output: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".

### Scoring

There are five set of tests, each set worth 2 points

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.

Added by: | Tata Dule |

Date: | 2012-12-08 |

Time limit: | 0.200s |

Source limit: | 50000B |

Memory limit: | 1536MB |

Cluster: | Cube (Intel G860) |

Languages: | All except: ASM32-GCC GAWK MAWK BC C-CLANG CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV ICK JS-MONKEY KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PY_NBC R RACKET RUST CHICKEN SED SQLITE SWIFT UNLAMBDA VB.NET |