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.

Source: codeforces | Difficulty: HARD
Tags: Geometry

Complete search


Solutions:
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.0)
gao()


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)


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)


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])
				if area > 0:
					if area > max_upper:
						max_upper = area
				elif -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)


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)


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)