Maximal Area Quadrilateral (Codeforces 340B)
Tags: Others, geometry

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: xi, yi ( - 1000 ≤ xi, yi ≤ 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.

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.

Sample Inputs:
5
0 0
0 4
4 0
4 4
2 3

Sample Outputs:
16.000000

Solution (Python):
def convex(v, eps=1e-08):
    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

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)

Solution (Python):
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-08:
            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)

Solution (Python):
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)