public class Simplex {
    public static void main(String[] args) throws Exception {
        // CS4234 lecture 2 numbers
        double[][] A = new double[][] {
            {1, 0},
            {0, 1},
            {1, 1}
        };
        double[] b = new double[] {
            200,
            300,
            400
        };
        double[] c = new double[] {
            1,
            6
        };

        LPSolver solver = new LPSolver(A, b, c);
        double[] solution = new double[2];
        System.out.println(solver.solve(solution)); // should be 1900.0

        for (double x : solution)
            System.out.print(x + " "); // should be 100.0 and 300.0
        System.out.println();
    }

    public static class LPSolver {
        static final double EPS = 1e-9;
        int m;
        int n;
        int[] B;
        int[] N;
        double[][] D;

        public LPSolver(double[][] A, double[] b, double[] c) {
            m = b.length;
            n = c.length;
            N = new int[n + 1];
            B = new int[m];
            D = new double[m + 2][n + 2];

            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    D[i][j] = A[i][j];
                }
                B[i] = n + i;
                D[i][n] = -1;
                D[i][n + 1] = b[i];
            }
            for (int i = 0; i < n; i++) {
                N[i] = i;
                D[m][i] = -1 * c[i];
            }
            N[n] = -1;
            D[m + 1][n] = 1;
        }

        void pivot(int r, int s) {
            double inv = 1.0 / D[r][s];
            for (int i = 0; i < m + 2; i++)
                if (i != r) for (int j = 0; j < n + 2; j++) if (j != s) D[i][j] -= D[r][j] * D[i][s] * inv;
            for (int j = 0; j < n + 2; j++) if (j != s) D[r][j] *= inv;
            for (int i = 0; i < m + 2; i++) if (i != r) D[i][s] *= -inv;
            D[r][s] = inv;
            int temp = B[r];
            B[r] = N[s];
            N[s] = temp;
        }

        boolean simplex(int phase) {
            int x = (phase == 1) ? m + 1 : m;
            while (true) {
                int s = -1;
                for (int j = 0; j <= n; j++) {
                    if (phase == 2 && N[j] == -1) continue;
                    if (s == -1 || D[x][j] < D[x][s] || D[x][j] == D[x][s] && N[j] < N[s]) s = j;
                }
                if (D[x][s] > -1 * EPS) return true;
                int r = -1;
                for (int i = 0; i < m; i++) {
                    if (D[i][s] < EPS) continue;
                    if (r == -1 || D[i][n + 1] / D[i][s] < D[r][n + 1] / D[r][s] || (D[i][n + 1] / D[i][s]) == (D[r][n + 1] / D[r][s]) && B[i] < B[r])
                        r = i;
                }
                if (r == -1) return false;
                pivot(r, s);
            }
        }

        double solve(double[] x) {
            int r = 0;
            for (int i = 1; i < m; i++) if (D[i][n + 1] < D[r][n + 1]) r = i;
            if (D[r][n + 1] < -EPS) {
                pivot(r, n);
                if (!simplex(1) || D[m + 1][n + 1] < -EPS) return Double.MIN_VALUE;
                for (int i = 0; i < m; i++)
                    if (B[i] == -1) {
                        int s = -1;
                        for (int j = 0; j <= n; j++)
                            if (s == -1 || D[i][j] < D[i][s] || D[i][j] == D[i][s] && N[j] < N[s]) s = j;
                        pivot(i, s);
                    }
            }
            if (!simplex(2)) return Double.MAX_VALUE;
            for (int i = 0; i < m; i++) if (B[i] < n) x[B[i]] = D[i][n + 1];
            return D[m][n + 1];
        }
    }
}