The happy Ender problem The happy ending problem (actually a theorem) states that


  Any set of five points in the plane in general position has a subset of four points that form the vertices of a convex quadrilateral.


The problem was so named by Paul Erdős when two mathematicians who first worked on the problem, Ester Klein and George Szekeres, became engaged and subsequently married.

Clarifications:


General position here means that no three points are collinear.
The quadrilateral formed by the four vertices will always be considered to be non-intersecting, irrespective of the order of the points. For example, given the four points [1 1], [1 2], [2 1], [2 2] the intended quadrilateral is the square, not the bow-tie:


A non-intersecting quadrilateral is convex if no interior angle exceeds 180 degrees; or equivalently if both diagonals lie inside the quadrilateral.


The challenge

Given 5 points with positive integer coordinates, output 4 of those points that form a convex quadrilateral.

Rules

If there are several solutions (that is, several sets of 4 points), you can consistently choose to output one of them or all.

Input and output formats are flexible as usual (arrays, lists, list of lists, strings with reasonable separators, etc).

Code golf, fewest bytes wins.

Test cases


Input:

[6 8] [1 10] [6 6] [5 9] [8 10]


There is only one possible output:

[6 8] [1 10] [6 6] [5 9]

Input:

[3 8] [7 5] [6 9] [7 8] [5 1]


There are five solutions:

[3 8] [7 5] [6 9] [7 8]
[3 8] [7 5] [6 9] [5 1]
[3 8] [7 5] [7 8] [5 1]
[3 8] [6 9] [7 8] [5 1]
[7 5] [6 9] [7 8] [5 1]

Input:

[4 8] [1 9] [9 9] [10 2] [1 6]


There are three solutions:

[4 8] [1 9] [10 2] [1 6]
[4 8] [9 9] [10 2] [1 6]
[1 9] [9 9] [10 2] [1 6]


To illustrate, here are the three solutions to this case:
CJam, 37 34 32 bytes

{e!Wf&lt;{2*3ew{)f.-~W%.*:-V&gt;},!}=}


Not sure if :-V is happy enough, but as K Zhang points out, there's the =} at the end. :)

This only prints one solution because removing duplicates would be more expensive.

Test it here.

Explanation

The idea is fairly simple. We generate all possible quadrilaterals (including all orderings of the points) and then just select the convex ones. We test convexity by looking at every pair of edges and checking that they're all turning in the same direction. 

The turning sense can be obtained quite easily from a dot product. If you take the three consecutive points on a quadrilateral, and draw lines from the first to the second, and the first to the third, and then project the latter onto the perpendicular of the former... you get a number whose sign tells you whether these three points turn left or right. (I should probably add a diagram for this.) This "projecting onto the perpendicular" is sounds quite involved, but really just means that we reverse one of the two vectors and subtract the components after multiplication instead of adding them. So here's the code...

e!       e# Generate all permutations of the five input points.
Wf&lt;      e# Discard the fifth point in each permutations, giving all
         e# possible quadrilaterals.
{        e# Select the first for which this block gives a truthy result...
  2*     e#   Double the list of points, so that it includes each cyclically
         e#   adjacent set of three points.
  3ew    e#   Get all sublists of length 3, i.e. all sets of three consecutive
         e#   points (with two duplicates).
  {      e#   Filter these sets of three points...
    )    e#     Pull off the last point.
    f.-  e#     Subtract it from the other two, giving vectors from it to
         e#     to those.
    ~    e#     Unwrap the array dumping both vectors on the stack.
    W%   e#     Reverse one of them.
    .*   e#     Element-wise multiplication.
    :-   e#     Subtract the second element from the first. This completes
         e#     the projection.
    V&gt;   e#     Check whether it's greater than 0. This is *false* for right-
         e#     turning sets of three points.
  },     e#   If all corners are right-turning, this will result
         e#   in an empty array.
  !      e#   Logical NOT - hence, only quadrilaterals where all corners
         e#   are right-turning give something truthy.
}=