  # Résolution de problèmes algorithmiques

Given 4 points, place them in clockwise order and determine the shape formed by these points: square, rectangle, rhombus, parallelogram, trapezium or ordinary quadrilateral.

## Elementary tests

A point is represented as a tuple. Given 3 points a, b, c we can ask if the walk a to b to c is a left turn. This is done by computing this simple expression. Similarly we can test whether the segments a-b and b-c are perpendicular, or if two segments are parallel. All these tests reduce to computing the determinant of some 2 by 2 matrix.

## Sorting the points

We know that no 3 points of the given 4 points are co-linear. This means that the points are on their convex hull. So we would like to place the points in such an order such that any 3 consecutive points form a left turn. Let the points be p0, p1, p2 and p3. We can do bubble sort to find the right order. First we test the orientation of p0, p1, p2 and swap p1, p2 if necessary. Then we know that these 3 points are in order. We just need to find the correct position of p3, by comparing it with p2 and then p1.

## Testing the shapes

To test the actual shapes, we first determine the lengths of the sides, tests if opposite sides are parallel and test if some angle is of 90 degrees. Then we can test the conditions of the different shapes in reverse order of priority. Note that for rectangles, once opposite sides have the same lengths it is not necessary to test all angles, one is enough. Also note that we compare the squares of the lengths rather than the actual lengths, this avoids loss of precision due to the square root.

## Note

Our Python solution is too slow for the UVA judge. The main problem could be the slow I/O of Python.