You are given a convex polygon $P$ with vertices $P_0, P_1, \ldots, P_{n-1}$, each having integer coordinates. On each edge $P_{i} P_{(i+1) \% n}$ of the polygon, choose a point $R_i$ uniformly at random. What is the expected area of the convex hull of these $n$ chosen points $R_0, R_1, \ldots R_{n-1}$ ?

-----Note-----
- Consider the area of the convex hull as zero if it contains less than 3 vertices.
- All the points $R_i$ are chosen independently of each other.
- Your answer is considered correct if and only if its absolute or relative error doesn't exceed $10^{-6}$.

-----Input-----
- The first line contains $n$, the number of vertices in the convex polygon.
- The next $n$ lines contain the coordinates of the vertices of the polygon in anti-clockwise order. 

-----Output-----
For each testcase, print the expected area of the convex hull of the $n$ randomly chosen points.

-----Constraints-----
- $3 \leq n \leq 10^5$
- The absolute values of all the coordinates $\leq 10^7$.
- All the points in the input are distinct.
- The described polygon $P$ is convex and the vertices of the polygon are given in anti-clockwise order. Also, no three vertices of the polygon are collinear.

-----Example Input-----
3
0 0
1 0
0 1

-----Example Output-----
0.1250000000

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
n = int(input())
x = []
y = []
for _ in range(n):
	s = input().split(' ')
	x.append(int(s[0]))
	y.append(int(s[1]))
q = x[0]
w = y[0]
for t in range(n - 1):
	x[t] = (x[t] + x[t + 1]) / 2
	y[t] = (y[t] + y[t + 1]) / 2
x[n - 1] = (x[n - 1] + q) / 2
y[n - 1] = (y[n - 1] + w) / 2
i = 0
a = 0
while i < n - 1:
	a += (x[i] * y[i + 1] - y[i] * x[i + 1]) / 2
	i += 1
a += (x[i] * y[0] - y[i] * x[0]) / 2
print(abs(a))


def func(a, n):
	if n < 3:
		return 0
	res_arr = []
	for i in range(n):
		x = (a[i][0] + a[(i + 1) % n][0]) / 2
		y = (a[i][1] + a[(i + 1) % n][1]) / 2
		res_arr.append((x, y))
	l = len(res_arr)
	s = 0
	for i in range(n):
		u = res_arr[i][0] * res_arr[(i + 1) % l][1]
		v = res_arr[i][1] * res_arr[(i + 1) % l][0]
		s += u - v
	return abs(s) / 2

def __starting_point():
	n = int(input())
	arr = []
	for i in range(n):
		(x, y) = map(int, input().split())
		arr.append((x, y))
	res = func(arr, n)
	print(res)
__starting_point()


import numpy as np

def PolyArea(x, y):
	return 0.5 * np.abs(np.dot(x, np.roll(y, 1)) - np.dot(y, np.roll(x, 1)))
n = int(input())
a = []
b = []
for i in range(0, n):
	(a1, b1) = input().split(' ')
	(a1, b1) = (int(a1), int(b1))
	a.append(a1)
	b.append(b1)
a1 = []
b1 = []
for i in range(0, n - 1):
	a1.append((a[i] + a[i + 1]) / 2)
	b1.append((b[i] + b[i + 1]) / 2)
a1.append((a[0] + a[-1]) / 2)
b1.append((b[0] + b[-1]) / 2)
print(PolyArea(np.array(a1), np.array(b1)))


def polygonArea(X, Y, n):
	area = 0.0
	j = n - 1
	for i in range(0, n):
		area += X[j] * Y[i] - Y[j] * X[i]
		j = i
	return abs(area / 2.0)
X = []
Y = []
xy = []
n = int(input())
for i in range(n):
	xy.append(list(map(int, input().split())))
for i in range(n - 1):
	X.append((xy[i][0] + xy[i + 1][0]) / 2)
	Y.append((xy[i][1] + xy[i + 1][1]) / 2)
X.append((xy[0][0] + xy[n - 1][0]) / 2)
Y.append((xy[0][1] + xy[n - 1][1]) / 2)
print(polygonArea(X, Y, n))


x = []
y = []
n = int(input())
for i in range(n):
	(a, b) = list(map(int, input().split()))
	x.append(a)
	y.append(b)
(a, b) = ([], [])
for i in range(-1, n - 1):
	a.append((x[i] + x[i + 1]) / 2)
	b.append((y[i] + y[i + 1]) / 2)

def polygonArea(X, Y, n):
	area = 0.0
	j = n - 1
	for i in range(n):
		area += (X[j] + X[i]) * (Y[j] - Y[i])
		j = i
	return abs(area / 2)
print(polygonArea(a, b, n))