Your browser (Unknown 0) is no longer supported. Some parts of the website may not work correctly. Please update your browser.

#### Minfuds

Compute minimal value of the function (max f_n) - (min f_n).

Two non-empty arrays A and B, each consisting of N integers, are given. Four functions are defined based on these arrays:

 F(X,K) = A[K]*X + B[K] U(X) = max{ F(X,K) : 0 ≤ K < N } D(X) = min{ F(X,K) : 0 ≤ K < N } S(X) = U(X) − D(X)

Write a function:

class Solution { public double solution(int[] A, int[] B); }

that, given two arrays A and B consisting of N integers each, returns the minimum value of S(X) where X can be any real number.

For example, given the following arrays A and B consisting of three elements each:

A = -1 B = 3 A = 1 B = 0 A = 0 B = 2

the function should return 0.5 because:

 U(X) = −1*X + 3 if X ≤ 1 U(X) = 0*X + 2 if 1 ≤ X ≤ 2 U(X) = 1*X + 0 if 2 ≤ X

and:

 D(X) = 1*X + 0 if X ≤ 1.5 D(X) = −1*X + 3 if 1.5 ≤ X

so for X = 1.5, function S(X) is equal to 0.5 and this is the minimum value of this function.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of arrays A, B is an integer within the range [−1,000..1,000].