https://codility.com/programmers/task/minfuds
https://github.com/phiphy/codility/blob/master/minfuds-Epsilon_2011.c
Two non-empty zero-indexed 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:
double solution(int A[], int B[], int N);
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[0] = -1 B[0] = 3
A[1] = 1 B[1] = 0
A[2] = 0 B[2] = 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.
Assume that:
- 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].
Complexity:
- expected worst-case time complexity is O(N*log(N));
- expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements of input arrays can be modified.
由于n条直线最多有O(n^2)的交点，而题目要求的时间复杂度是O(nlgn)，明显暗示就是需要排序…… 所以，首先根据斜率对直线排序，斜率相同的情况下再按截距反向排。从前往后扫描排序好的直线，求出相邻直线的交点，如果该交点比前一个交点的x值还要小，则需要重新计算交点 （这个画个图最清楚了，我很懒就不画了，哈哈），求出的是定义maximum的所有交点。再从后往前扫描排序好的直线，得出定义minimum的所有交点。最后同时对两部分交点扫描，求出每个交点对应在另外一部分的值，计算y值之差后更新全局变量。
