import java.util.*; public class sandart_font { public static void main(String[] args) { new sandart_font(new Scanner(System.in)); } int N, M, W, H; double oo = 987654321.0; double[] upperSandBound, divider; double[][] lowerMat, upperMat; double getVolume(int i, double h) { return h*(divider[i+1]-divider[i]); } // Max and min allowed per color boolean isPossible(double minHeight, double maxHeight) { ArrayList graph = new ArrayList(); double[] balance = new double[N+M+2]; // The nodes are numbered: // colors [0,M) // sections [M, N+M) // s = N+M // t = N+M+1 int s = N+M, t = N+M+1; // Connect edges source to sink that represent the color boundaries for (int i=0; i e.hi) System.out.printf("BADNESS: Flow bound conflict! %.3f %.3f%n", e.lo, e.hi); // Add an edge for the remaining capacity tf.add(e.i, e.j, e.hi-e.lo); } // Since balance is conserved the sum of the deficit equals the // sum of the excess. We only have to find one of these values. double target = 0.0; ArrayList leaving = new ArrayList(); for (int i=0; i 0) { target += balance[i]; leaving.add(tf.add(tf.s, i, balance[i])); } else tf.add(i, tf.t, -balance[i]); } // Run flow and make sure the graph is saturated double flow = tf.getFlow(); return Math.abs(target-flow) < 1e-6; } public sandart_font(Scanner in) { N = in.nextInt(); M = in.nextInt(); W = in.nextInt(); H = in.nextInt(); if (N < 2 || N > 200) System.out.println("INVALID N"); if (M < 1 || M > 200) System.out.println("INVALID M"); if (W < 1 || W > 5_000) System.out.println("INVALID W"); if (H < 1 || H > 5_000) System.out.println("INVALID H"); upperSandBound = new double[M]; for (int i=0; i= upperSandBound[i] || W*H < upperSandBound[i]) System.out.println("INVALID USB"); } divider = new double[N+1]; divider[0] = 0; divider[N] = W; for (int i=1; i= W) System.out.println("DIVIDER OUTSIDE RANGE"); } for (int i=1; i<=N; i++) if (divider[i-1] >= divider[i]) System.out.println("INVALID DIVIDER INVARIANT"); lowerMat = new double[N][M]; for (int i=0; i W*H) System.out.println("BAD LOWER MATRIX VALUE"); } upperMat = new double[N][M]; for (int i=0; i W*H) System.out.println("BAD UPPER MATRIX VALUE"); if (lowerMat[i][j] > upperMat[i][j]) System.out.println("BAD MATRIX INVARIANT"); } double lo=0, hi=H; for (int i=0; i capacity) { System.out.printf("overcommitted %d %.3f %.3f%n", i, used, capacity); return; } double percentageFilled = used / capacity; lo = Math.max(lo, percentageFilled); } double loConstraint = lo; if (!isPossible(lo, H)) { System.out.println("unsatisfiable"); return; } for (int step=0; step<200 && hi-lo > 1e-9; step++) { double m = (hi+lo)*0.5; if (isPossible(m, H)) lo = m; else hi = m; } double loBound = Math.max(loConstraint, lo-1e-9); hi = H; for (int step=0; step<200 && hi-lo > 1e-9; step++) { double m = (hi+lo)*0.5; if (isPossible(loBound, m)) hi = m; else lo = m; } double res = hi-loBound; System.out.printf("%.3f%n", res); } } class TidalFlow { ArrayDeque stk = new ArrayDeque(); int N, s, t, fptr, bptr; double oo = Long.MAX_VALUE*1.0; ArrayList[] adj; int[] q, dist; double[] pool; TidalFlow(int NN) { N=(t=(s=NN)+1)+1; adj = new ArrayList[N]; for (int i=0; i()); dist = new int[N]; pool = new double[N]; q = new int[N]; } Edge add(int i, int j, double cap) { Edge fwd = new Edge(i, j, cap, 0); Edge rev = new Edge(j, i, 0, 0); adj[i].add(rev.rev=fwd); adj[j].add(fwd.rev=rev); return fwd; } double augment() { Arrays.fill(dist, Integer.MAX_VALUE); pool[t] = dist[s] = fptr = bptr = 0; pool[q[bptr++] = s] = oo; while (bptr > fptr && q[fptr] != t) { for (Edge e : adj[q[fptr++]]) { if (dist[e.i] < dist[e.j]) pool[e.j] += e.carry = Math.min(e.cap - e.flow, pool[e.i]); if (dist[e.i] + 1 < dist[e.j] && e.cap > e.flow) dist[q[bptr++] = e.j] = dist[e.i] + 1; } } if (dist[t] == Integer.MAX_VALUE) return 0; Arrays.fill(pool, fptr = bptr = 0); pool[q[bptr++] = t] = oo; while (bptr > fptr) { for (Edge e : adj[q[fptr++]]) { if (pool[e.i] == 0.0) break; double f = e.rev.carry = Math.min(pool[e.i], e.rev.carry); if (dist[e.i] > dist[e.j] && f > 0) { if (pool[e.j] == 0) q[bptr++] = e.j; pool[e.i] -= f; pool[e.j] += f; stk.push(e.rev); } } } double res = pool[s]; Arrays.fill(pool, 0); pool[s] = res; while (stk.size() > 0) { Edge e = stk.pop(); double f = Math.min(e.carry, pool[e.i]); pool[e.i] -= f; pool[e.j] += f; e.flow += f; e.rev.flow -= f; } return res; } double getFlow() { for (int i=0; i