Magic Hull

You are given a set of N twodimensional nonzero vectors (X_{1}, Y_{1}), (X_{2}, Y_{2}), ..., (X_{N}, Y_{N}) with integer coordinates. You can choose no more than 6 vectors from this set to form a nonstrictly convex polygon that have sides equal to these vectors (see paragraph below for more detailed explanation). Nonstrictly convex polygon is the polygon that can have flat angles (angles of 180 degrees). You can select each vector several times if needed. Your goal is to maximize the area of this polygon. It is guaranteed that at least one such convex polygon can be constructed.
How exactly we construct a polygon from the given sequence of vectors? Suppose you've chosen the sequence of vectors (U_{1}, V_{1}), (U_{2}, V_{2}), ..., (U_{K}, V_{K}), where 3 ≤ K ≤ 6. Each vector here should be equal to one of the given N vectors but some vectors in this sequence can coincide. At first, you take some point (A_{1}, B_{1}) at the plane as the first vertex of your polygon. Then you put your first vector (U_{1}, V_{1}) to this point to obtain the second vertex (A_{2}, B_{2}) = (A_{1} + U_{1}, B_{1} + V_{1}). Next you take the second vector and put it to the second vertex to obtain the third vertex and so on. Finally, at the last step you put vector (U_{K}, V_{K}) to the K^{th} vertex (A_{K}, B_{K}) to obtain the point (A_{K + 1}, B_{K + 1}) = (A_{K} + U_{K}, B_{K} + V_{K}) that should coincide with the first vertex (A_{1}, B_{1}), otherwise we should reject this sequence of vectors. Hence in the end we obtain a polygon with vertexes (A_{1}, B_{1}), (A_{2}, B_{2}), ..., (A_{K}, B_{K}). If this polygon is simple (without selfintersections) and nonstrictly convex, we should consider its area as the candidate for the answer. By selfintersection we mean that either some nonconsecutive sides (considered with their ends) have common point or two consecutive sides have more than one common point.
Input
The first line of the input file contains an integer N, the number of the given vectors. Each of the following N lines contains two space separated integers X_{i}, Y_{i}, coordinates of the corresponding vector.
Output
In the only line of the output file print the maximal possible area of the convex polygon that can be constructed by the rules described in the problem statement with exactly one digit after the decimal point.
Constraints
3 ≤ N ≤ 150
X_{i}, Y_{i} ≤ 1000000
All vectors are nonzero: X_{i} + Y_{i} > 0
There exists at least one sequence of at most 6 vectors from this set that forms a convex polygon.
Example
Input: 4 3 0 1 1 1 0 1 1 Output: 2.0
Explanation
The only nonstrictly convex polygon you can construct from these vectors by the rules described in the problem statement is the isosceles trapezoid that has height of length 1 and bases of length 1 and 3. It has area 2.0.
Author:  shangjingbo 
Tags  june12, medium, polygons, shangjingbo, vectors 
Date Added:  29032012 
Time Limit:  0.5  0.503465 sec 
Source Limit:  50000 Bytes 
Languages:  C, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions