Minimum Convex Polygon Area

Nana’s electronic pet, MACARON, enjoys moving around in the room. Nana wants to create a bounded area where MACARON can roam within. She provides a set of vertices representing positions in the room and would like to select a subset of these vertices to form a convex polygon such that the area of the polygon is minimized.

A convex polygon must have at least three non-collinear points. Hence, the task boils down to choosing at least three points (forming a triangle or a polygon with more vertices) from the given set that results in the smallest possible area. Notice that any triangle with a non-zero area is a convex polygon. Therefore, the problem can be reduced to finding the triangle with the minimal positive area.

The area of a triangle formed by three points \((x_1,y_1)\), \((x_2,y_2)\), and \((x_3,y_3)\) is given by:

$$ Area = \frac{|x_1(y_2 - y_3) + x_2(y_3 - y_1) + x_3(y_1 - y_2)|}{2} $$

If no such convex polygon (i.e. no three non-collinear points) exists, output -1.

inputFormat

The first line contains an integer \(N\) \((3 \leq N \leq 10^3)\) representing the number of points.

Each of the following \(N\) lines contains two integers \(x\) and \(y\) \((-10^4 \leq x,y \leq 10^4)\), denoting the coordinates of a point.

outputFormat

Output a single line containing the minimum area of a convex polygon that can be formed using a subset of the given vertices. If no convex polygon exists, output -1.

sample

3
0 0
1 0
0 1

0.5