Quadrilateral blanket

Time limit5sMemory limit128 MB

Summary

Given N points and an area limit L, pick four points forming a simple quadrilateral with area at most L, maximizing that area.

Level: Hard8 of 10
Topics: Geometry, Brute force, Sorting, Binary search
Solved: No attempts yet

Problem

Mirko likes daisies. Every time he organizes a picnic he makes himself a new blanket shaped like a quadrilateral. When he spreads the blanket on the meadow, he wants the four corners of the quadrilateral to sit exactly on daisies that grow there. His group is large, so he wants the blanket to be as big as possible, but he has only $L$ square meters of cloth, so the area of the blanket must be at most $L$ .

You are given the coordinates of $N$ daisies in the meadow. Choose four distinct daisies as the corners of the blanket and find the largest area that is at most $L$ .

The blanket does not have to be convex, but its area must be greater than 0. Mirko is a skilled tailor, so he cuts and glues the cloth freely and can build any quadrilateral shape. Three of the four corners may lie on one line. The sides must not cross each other, and two adjacent sides may meet only at the corner they share.

Input

The first line contains the number of daisies $N$ and the area of cloth Mirko has, $L$ . ( $4 \le N \le 300$ , $1 \le L \le 10^9$ )

Each of the next $N$ lines contains two integers $x$ and $y$ , the coordinates of one daisy. ( $-10000 \le x, y \le 10000$ ) No two daisies grow at the same coordinates.

Output

Print the largest area of a blanket that satisfies the conditions, with exactly two digits after the decimal point. The area is always a multiple of 0.5, so no rounding error occurs. If no blanket satisfies Mirko's wish, print 0.00.

Examples3

Example 1
Input
```
4 7
-1 -1
-1 1
1 1
1 -1
```
Expected output
```
4.00
```

Example 2

Input

Expected output

21.00

Example 3

Input

Expected output

0.00