Problem:
 Score : 1300 points    Problem Statement You are playing a game and your goal is to maximize your expected gain.
At the beginning of the game, a pawn is put, uniformly at random, at a position p\in\{1,2,\dots, N\} . The N positions are arranged on a circle (so that 1 is between N and 2 ).  The game consists of turns. At each turn you can either end the game, and get A_p dollars (where p is the current position of the pawn), or pay B_p dollar to keep playing.
If you decide to keep playing, the pawn is randomly moved to one of the two adjacent positions p-1 , p+1 (with the identifications 0 = N and N+1=1 ).  What is the expected gain of an optimal strategy?  Note : The "expected gain of an optimal strategy" shall be defined as the supremum of the expected gain among all strategies such that the game ends in a finite number of turns.      Constraints  2 \le N \le 200,000  0 \le A_p \le 10^{12} for any p = 1,\ldots, N  0 \le B_p \le 100 for any p = 1, \ldots, N  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A_1  A_2  \cdots  A_N  B_1  B_2  \cdots  B_N       Output Print a single real number, the expected gain of an optimal strategy. 
Your answer will be considered correct if its relative or absolute error does not exceed 10^{-10} .        Sample Input 1 5
4 2 6 3 5
1 1 1 1 1      Sample Output 1 4.700000000000       Sample Input 2 4
100 0 100 0
0 100 0 100      Sample Output 2 50.000000000000       Sample Input 3 14
4839 5400 6231 5800 6001 5200 6350 7133 7986 8012 7537 7013 6477 5912
34 54 61 32 52 61 21 43 65 12 45 21 1 4      Sample Output 3 7047.142857142857       Sample Input 4 10
470606482521 533212137322 116718867454 746976621474 457112271419 815899162072 641324977314 88281100571 9231169966 455007126951
26 83 30 59 100 88 84 91 54 61      Sample Output 4 815899161079.400024414062

Solution (Python):
import numpy as np

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

a = np.array(A, dtype=float)
b = np.array(B, dtype=float)

argmaxA = a.argmax()
a = np.roll(a, -argmaxA)
b = np.roll(b, -argmaxA + 1)
a = np.append(a, a[0])
b = np.append(b, b[0])
bb = np.cumsum(b)
c = 2 * np.cumsum(bb)


c -= c[0]
c -= np.arange(N + 1) * ((c[-1] - c[0]) / (N))
c += a[0]

a_c = a - c


def signed_area(x1, y1, x2, y2, x3, y3):
    x12 = x2 - x1
    y12 = y2 - y1
    x13 = x3 - x1
    y13 = y3 - y1
    return x12 * y13 - x13 * y12



vertices = [(0, a_c[0]), (1, a_c[1])]
for i in range(2, N + 1):
    while (
        len(vertices) >= 2 and signed_area(*vertices[-2], *vertices[-1], i, a_c[i]) >= 0
    ):
        vertices.pop()

    vertices.append((i, a_c[i]))

ans = 0
for i in range(len(vertices) - 1):
    ans += (vertices[i + 1][0] - vertices[i][0]) * (vertices[i + 1][1] + vertices[i][1])
ans /= N * 2
ans += c[:-1].mean()
print(ans)

Solution (Python):
from math import gcd

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

class Seg_min():
    def __init__(self,x):
        
        self.ide_ele_min = 10**10
        self.func = min

        self.n = len(x)

        
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res


class Seg_max():
    def __init__(self,x):
        
        self.ide_ele_min = 10**10 * -1
        self.func = max

        self.n = len(x)

        
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res


max_ind = 0
max_num = -1
for ind,i in enumerate(a):
    if(i > max_num):
        max_ind = ind
        max_num = i


a = a[max_ind:] + a[:max_ind]
b = b[max_ind:] + b[:max_ind]


order = [(i,ind) for ind,i in enumerate(a)]
order.sort()




cs1_l = [0] * (n)
cs2_l = [0] * (n)
cs1_r = [0] * (n+1)
cs2_r = [0] * (n+1)

for i in range(1,n):
    cs1_l[i] = cs1_l[i-1] + b[i]
    cs2_l[i] = cs2_l[i-1] + b[i]*i

for i in range(1,n):
    cs1_r[-(i+1)] = cs1_r[-i] + b[-i]
    cs2_r[-(i+1)] = cs2_r[-i] + b[-i]*i


a.append(a[0])
b.append(b[0])


seg_left = Seg_max( list(range(n+1)) )
seg_right = Seg_min( list(range(n+1)) )


end = [1] * (n+1)




def calc_ex(ind):
    left = seg_left.query(0,ind)
    right = seg_right.query(ind+1,n+1)

    div = right - left
    wid_l = ind-left
    wid_r = right-ind
    
    base = cs2_l[ind] - cs2_l[left] - (cs1_l[ind] - cs1_l[left])*left
    ex_l = base*2 * wid_r

    
    base = cs2_r[ind] - cs2_r[right] - (cs1_r[ind] - cs1_r[right])*(n-right)
    ex_r = base*2 * wid_l

    ex = -ex_l - ex_r + b[ind]*wid_l*wid_r*2 + a[left]*wid_r + a[right]*wid_l

    return ex,div




order = [j for i,j in order][::-1]
flag = True
while(flag):
    flag = False
    while(order):
        ind = order.pop()
        if(ind==0):
            continue
        if(end[ind]==0):
            continue

        ex,div = calc_ex(ind)
        if(a[ind]*div < ex):
            end[ind] = 0
            seg_left.update(ind,0)
            seg_right.update(ind,n)

            left = seg_left.query(0,ind)
            right = seg_right.query(ind+1,n+1)
            if(left!=0):
                order.append(left)
            if(right!=n):
                order.append(right)
            flag = True

    if(flag):
        for i,val in enumerate(end[:-1]):
            if(val==1):
                order.append(i)


ans = [0] * (n)
for ind,flag in enumerate(end[:-1]):
    if(flag==1):
        ans[ind] = (a[ind],1)
    else:
        ex,div = calc_ex(ind)
        ans[ind] = (ex,div)

lcm = 1
for ex,div in ans:
    lcm = (lcm*div)//gcd(lcm,div)

ans_num = 0
for ex,div in ans:
    ans_num += ex*(lcm//div)

print(ans_num/(lcm*n))

Solution (Python):
from bisect import bisect_right


def det(p1, p2, p3):
    area = (p2[0] - p1[0])*(p3[1] - p1[1]) - (p2[1] - p1[1])*(p3[0] - p1[0])
    return area > 0


def convex_hull(pts):
    pts = sorted(pts)
    n = len(pts)
    extsize = 0
    extpts = []
    for i in range(n):
        while extsize > 1:
            if det(extpts[-2], extpts[-1], pts[i]):
                break
            extsize -= 1
            extpts.pop()
        extpts.append(pts[i])
        extsize += 1
    t = extsize
    for i in range(n-1, -1, -1):
        while extsize > t:
            if det(extpts[-2], extpts[-1], pts[i]):
                break
            extsize -= 1
            extpts.pop()
        extpts.append(pts[i])
        extsize += 1
    return extpts[:-1]


n = int(input())
aa = [int(x) for x in input().split()]
bb = [int(x) for x in input().split()]

ma = max(aa)
ind = -1
for i in range(n):
    if ma == aa[i]:
        ind = i
        break

a = aa[i:] + aa[:i+1]
b = bb[i:] + bb[:i+1]

c = [0]*(n+1)
for i in range(2, n+1):
    c[i] = 2*(c[i-1]+b[i-1])-c[i-2]

pts = []
for i in range(n+1):
    pts.append((i, a[i]-c[i]))

f = [-10**15]*(n+1)
ext = []

for i, val in convex_hull(pts):
    if val*n < (a[0]-c[0])*(n-i)+(a[n]-c[n])*i:
        continue
    f[i] = val
    ext.append(i)

ext = sorted(ext)

for i in range(n+1):
    if f[i] == -10**15:
        t = bisect_right(ext, i)
        l = ext[t-1]
        r = ext[t]
        f[i] = f[l] + (i-l)*(f[r]-f[l])/(r-l)


ans = 0
for i in range(1, n+1):
    ans += f[i]+c[i]

print(f'{ans/n:.12f}')