Iahub has drawn a set of n points in the cartesian plane which he calls "special points". A quadrilateral is a simple polygon without self-intersections with four sides (also called edges) and four vertices (also called corners). Please note that a quadrilateral doesn't have to be convex. A special quadrilateral is one which has all four vertices in the set of special points. Given the set of special points, please calculate the maximal area of a special quadrilateral. 


-----Input-----

The first line contains integer n (4 ≤ n ≤ 300). Each of the next n lines contains two integers: x_{i}, y_{i} ( - 1000 ≤ x_{i}, y_{i} ≤ 1000) — the cartesian coordinates of ith special point. It is guaranteed that no three points are on the same line. It is guaranteed that no two points coincide. 


-----Output-----

Output a single real number — the maximal area of a special quadrilateral. The answer will be considered correct if its absolute or relative error does't exceed 10^{ - 9}.


-----Examples-----
Input
5
0 0
0 4
4 0
4 4
2 3

Output
16.000000


-----Note-----

In the test example we can choose first 4 points to be the vertices of the quadrilateral. They form a square by side 4, so the area is 4·4 = 16.

Difficulty: interview

Starter code:

Solutions:
# calculate convex of polygon v.
# v is list of complexes stand for points.
def convex(v, eps=1e-8):

    # fetch the seed point
    v.sort(key=lambda x:(x.real,x.imag))
    v = v[0:1] + sorted(v[1:], key=lambda x:(x-v[0]).imag/abs(x-v[0]))

    n = 1
    for i in range(2, len(v)):
        while n > 1 and ((v[n]-v[n-1])*(v[i]-v[n]).conjugate()).imag>-eps:
            n -= 1
        else:
            n += 1
            v[n] = v[i]

    v[n+1:] = []

    return v

# calculate the area of a polygon v, anti-clockwise.
# v is list of complexes stand for points.
def area(v):
    ans = 0
    for i in range(2, len(v)):
        ans += ((v[i]-v[i-1])*(v[i-1]-v[0]).conjugate()).imag
    return ans * 0.5

n = int(input())
v = [complex(*tuple(map(int, input().split()))) for i in range(0, n)]

w = convex(v)
n = len(w)

ans = 0

def tri(i, j, k): return abs(((w[i]-w[j])*(w[i]-w[k]).conjugate()).imag) * 0.5

for i in range(0, n):
    
    for j in range(i+2, n):

        if i == 0 and j == n-1: continue
        
        l = i + 1
        r = j
        while l < r-1:
            k = l+r>>1
            if tri(i, j, k) > tri(i, j, k-1):
                l = k
            else:
                r = k
                
        s1 = tri(i, j, l)

        l = j - n + 1
        r = i
        while l < r-1:
            k = l+r>>1
            if tri(i, j, k) > tri(i, j, k-1):
                l = k
            else:
                r = k
        
        s2 = tri(i, j, l)

        ans = max(ans, s1 + s2)

if n == 3:
    for p in v:
        if not p in w:
            w.append(p)
            ans = max(ans, area(w))
            w.pop()
        
print(ans)


import sys
c, n = 0, int(input())
t = list(map(int, sys.stdin.read().split()))
p = [complex(t[i], t[i + 1]) for i in range(0, 2 * n, 2)]
for x, i in enumerate(p, 1):
    for j in p[x:]:
        a = b = 0
        for k in p:
            if k == i or k == j: continue
            d = (i.real - k.real) * (j.imag - k.imag) - (i.imag - k.imag) * (j.real - k.real)
            a, b = min(d, a), max(d, b)
        if a and b: c = max(c, b - a)
print(c / 2)

import sys
s, n = 0, int(input())
t = list(map(int, sys.stdin.read().split()))
p = [(t[2 * i], t[2 * i + 1]) for i in range(n)]
for x, i in enumerate(p, 1):
    for j in p[x:]:
        a = b = 0
        for k in p:
            d = (i[0] - k[0]) * (j[1] - k[1]) - (i[1] - k[1]) * (j[0] - k[0])
            a, b = min(d, a), max(d, b)
        if a and b: s = max(s, b - a)
print(s / 2)

def cross(x1, y1, x2, y2):
    return x1 * y2 - x2 * y1

def gao():
    n = int(input())
    x, y = [], []
    for i in range(n):
        x1, y1 = input().split(' ')
        x.append(int(x1))
        y.append(int(y1))

    max_area = 0
    for i in range(n):
        for j in range(i+1, n):
            max_left, max_right = 0, 0
            for k in range(n):
                if i != k and j != k:
                    area = cross(x[j] - x[i], y[j] - y[i], x[k] - x[i], y[k] - y[i])
                    if area > 0:
                        max_left = max(max_left, area)
                    elif area < 0:
                        max_right = max(max_right, -area)
            if max_left != 0 and max_right != 0:
                max_area = max(max_area, max_left + max_right)

    print(max_area / 2.)

gao()

n = int(input())
a = []
area = 0
for i in range(n):
    a.append([int(i) for i in input().split(' ')])


def get_s(p1, p2, p3):
    return ((p2[0] - p1[0]) * (p3[1] - p1[1]) - (p2[1] - p1[1]) * (p3[0] - p1[0])) / 2.0


for i in range(len(a) - 1):
    for j in range(i + 1, len(a)):
        positive = 0
        negative = 0
        for k in range(len(a)):
            if k == i or k == j:
                continue
            s = get_s(a[i], a[j], a[k])
            if s > 0:
                positive = max(positive, s)
            if s == 0:
                pass
            else:
                negative = min(negative, s)
        if positive != 0 and negative != 0:
            area = max(area, positive - negative)

print(area)



n = int(input())
l = []




def cross(x1,y1,x2,y2):

    area = x1*y2 - y1*x2
    return area


for i in range(n):
    x,y = list(map(int,input().split()))
    l.append([x,y])
max_upper = 0
max_lower = 0
ans = 0
for i in range(n-1):
    for j in range(i+1,n):
        max_upper = 0
        max_lower = 0
        for k in range(n):
          if i!=j and i!=k and j!=k:
            area = (l[j][0] - l[i][0])*(l[k][1] - l[i][1])-(l[j][1] - l[i][1])*(l[k][0] - l[i][0])
            # print(area/2)
            if area>0:
                if area>max_upper:
                    max_upper = area
            else:
                if -area>max_lower and area!=0:
                    max_lower = -area

        if max_lower + max_upper > ans and max_lower!=0 and max_upper!=0:
          ans = max_lower + max_upper
print(ans/2)





def convex(p):
    p.sort(key = lambda x:(x.real, x.imag))
    p = p[0:1] + sorted(p[1:], key = lambda x:(x-p[0]).imag / abs(x-p[0]))
    j = 1
    for i in range(2, len(p)):
        while j > 1 and ((p[j] - p[j-1]) * (p[i] - p[j]).conjugate()).imag > -(1e-8):
            j -= 1
        else:
            j += 1
            p[j] = p[i]
    return p[:j+1]

def area(p):
    res = 0
    for i in range(2, len(p)):
        res += ((p[i] - p[i-1]) * (p[i-1] - p[0]).conjugate()).imag
    return res * 0.5

def tri(i, j, k): 
    return abs(((w[i] - w[j]) * (w[i] - w[k]).conjugate()).imag) * 0.5

n = int(input())
p = [complex(*list(map(int, input().split()))) for i in range(n)]
w = convex(p)
n = len(w)
res = 0

for i in range(n):    
    for j in range(i+2, n):
        if i == 0 and j == n-1: 
            continue
        l, r = i + 1, j
        while l < r-1:
            m = l + r >> 1
            if tri(i, j, m) > tri(i, j, m-1):
                l = m
            else:
                r = m
        s1 = tri(i, j, l)
        l, r = j - n + 1, i
        while l < r-1:
            m = l + r >> 1
            if tri(i, j, m) > tri(i, j, m-1):
                l = m
            else:
                r = m
        s2 = tri(i, j, l)
        res = max(res, s1 + s2)

if n == 3:
    for i in p:
        if i in w:
            continue
        w.append(i)
        res = max(res, area(w))
        w.pop()        

print(res)


import sys
s, n = 0, int(input())
t = list(map(int, sys.stdin.read().split()))
p = [(t[2 * i], t[2 * i + 1]) for i in range(n)]
for x, i in enumerate(p, 1):
    for j in p[x:]:
        a = b = 0
        for k in p:
            d = (i[0] - k[0]) * (j[1] - k[1]) - (i[1] - k[1]) * (j[0] - k[0])
            a, b = min(d, a), max(d, b)
        if a and b: s = max(s, b - a)
print(s / 2)