You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
41 lines
1.0 KiB
Java
41 lines
1.0 KiB
Java
5 years ago
|
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));
|
||
|
|
}
|
||
|
|
}
|