Need Programming Assignment Help?

Get Help with Programming Assignment in Java, C/C++, Dot Net, PHP, Database and UML Diagrams

Convex Hull Optimization

Convex Hull Trick Implementation

Convex Hull Trick Implementation – This Data structure & Algorithm in Java is a Dynamic Programming example for Convex Hull Trick Implementation.

public class ConvexHullOptimization {

long[] A = new long[1000000];
 long[] B = new long[1000000];
 int len;
 int ptr;

// a descends
 public void addLine(long a, long b) {
 // intersection of (A[len-2],B[len-2]) with (A[len-1],B[len-1]) must lie to the left of intersection of (A[len-1],B[len-1]) with (a,b)
 while (len >= 2 && (B[len - 2] - B[len - 1]) * (a - A[len - 1]) >= (B[len - 1] - b) * (A[len - 1] - A[len - 2])) {
 --len;
 }
 A[len] = a;
 B[len] = b;
 ++len;
 }

// x ascends
 public long minValue(long x) {
 ptr = Math.min(ptr, len - 1);
 while (ptr + 1 < len && A[ptr + 1] * x + B[ptr + 1] <= A[ptr] * x + B[ptr]) {
 ++ptr;
 }
 return A[ptr] * x + B[ptr];
 }

// Usage example
 public static void main(String[] args) {
 ConvexHullOptimization h = new ConvexHullOptimization();
 h.addLine(3, 0);
 h.addLine(2, 1);
 h.addLine(3, 2);
 h.addLine(0, 6);
 System.out.println(h.minValue(0));
 System.out.println(h.minValue(1));
 System.out.println(h.minValue(2));
 System.out.println(h.minValue(3));
 }
}