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: interview

Starter code:

Solutions:
# cook your dish here
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))
#print(x,y)


# cook your dish here
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)))

# cook your dish here
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))

# cook your dish here
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): 
 
 # Initialze area 
 area = 0.0
 
 # Calculate value of shoelace formula 
 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))
  
 
 


# -*- coding: utf-8 -*-
"""
Created on Fri Dec 20 23:54:46 2019

@author: sj
"""
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)))