Dynamic Convex Hull

import java.util.*;

public class DynamicConvexHullTest {
    static class Line {
        // ax + b
        final long a, b;

        public Line(long a, long b) {
            this.a = a;
            this.b = b;
        }

        long getValue(long x) {
            return a * x + b;
        }

        @Override
        public String toString() {
            return "Line{" +
                    "a=" + a +
                    ", b=" + b +
                    '}';
        }
    }

    static class ConvexHull {
        // find max
        Line[] hull;

        ConvexHull(Line[] lines) {
            Arrays.sort(lines, new Comparator<Line>() {
                @Override
                public int compare(Line o1, Line o2) {
                    if (o1.b != o2.b) {
                        return -Long.compare(o1.b, o2.b);
                    }
                    return -Long.compare(o1.a, o2.a);
                }
            });
            int sz = 1;
            for (int i = 1; i < lines.length; i++) {
                while (sz > 1) {
                    Line l2 = lines[sz - 2], l1 = lines[sz - 1];
                    Line cur = lines[i];
                    double t1 = whenBetter(l2, l1), t2 = whenBetter(l1, cur);
                    if (t2 <= t1) {
                        sz--;
                    } else {
                        break;
                    }
                }
                lines[sz++] = lines[i];
            }
            hull = Arrays.copyOf(lines, sz);
        }

        double whenBetter(Line l1, Line l2) {
            // a1x + b1 < a2x + b2
            // x * (a1 - a2) < b2 - b1
            if (l1.a >= l2.a) {
                return Double.MAX_VALUE;
            }
            return (l1.b - l2.b) / (double) (l2.a - l1.a);
        }

        long getMax(long x) {
            if (hull.length == 1 || whenBetter(hull[0], hull[1]) > x) {
                return hull[0].getValue(x);
            }
            int l = 0, r = hull.length - 1;
            while (r - l > 1) {
                int m = (l + r) >> 1;
                if (whenBetter(hull[m], hull[m + 1]) > x) {
                    r = m;
                } else {
                    l = m;
                }
            }
            return hull[r].getValue(x);
        }

        static ConvexHull join(ConvexHull a, ConvexHull b) {
            Line[] allLines = new Line[a.hull.length + b.hull.length];
            System.arraycopy(a.hull, 0, allLines, 0, a.hull.length);
            System.arraycopy(b.hull, 0, allLines, a.hull.length, b.hull.length);
            return new ConvexHull(allLines);
        }
    }

    static class DynamicConvexHull {
        final int LOG = 20;
        ConvexHull[] hulls;

        DynamicConvexHull() {
            hulls = new ConvexHull[LOG];
        }

        void addConvexHull(ConvexHull convexHull) {
            int id = Math.min(LOG - 1, (int) (Math.log(convexHull.hull.length) / Math.log(2)));
            if (hulls[id] != null) {
                convexHull = ConvexHull.join(convexHull, hulls[id]);
                hulls[id] = null;
                addConvexHull(convexHull);
            } else {
                hulls[id] = convexHull;
            }
        }

        void addLine(Line l) {
            ConvexHull hull = new ConvexHull(new Line[]{l});
            addConvexHull(hull);
        }

        long getMax(long x) {
            long res = Long.MIN_VALUE;
            for (ConvexHull hull : hulls) {
                if (hull == null) {
                    continue;
                }
                res = Math.max(res, hull.getMax(x));
            }
            return res;
        }

    }

    static long slowFindMax(List<Line> lines, long pos) {
        long res = Long.MIN_VALUE;
        for (Line l : lines) {
            res = Math.max(res, l.getValue(pos));
        }
        return res;
    }

    public static void main(String[] args) {
        Random rnd = new Random(123);
        final int MAX = 1000;
        for (int it = 0; it < 123123; it++) {
            System.err.println("it = " + it);
            final int lines = 1 + rnd.nextInt(100);
            DynamicConvexHull dynamicConvexHull = new DynamicConvexHull();
            List<Line> usedLines = new ArrayList<>();
            for (int i = 0; i < lines; i++) {
                Line l = new Line(rnd.nextInt(MAX) - MAX / 2, rnd.nextInt(MAX) - MAX / 2);
                usedLines.add(l);
                dynamicConvexHull.addLine(l);
                long pos = rnd.nextInt(MAX);
                long checkedMax = dynamicConvexHull.getMax(pos);
                long correctMax = slowFindMax(usedLines, pos);
                if (checkedMax != correctMax) {
                    throw new AssertionError("Incorrect max: " + correctMax + ", fast = " + checkedMax + ", i = " + i + ", pos = " + pos);
                }
            }
        }
    }
}