#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<int> VI;

const double EPS = 1e-9;

struct Simplex {
    int m, n;
    VI B, N;
    VVD D;

    Simplex(const VVD &A, const VD &b, const VD &c) :
        m(b.size()), n(c.size()), B(m), N(n + 1), D(m + 2, VD(n + 2)) {
        
        for (int i = 0; i < m; ++i) B[i] = n + i;
        for (int j = 0; j < n; ++j) N[j] = j;
        N[n] = -1;
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) D[i][j] = A[i][j];
            D[i][n] = -1;
            D[i][n + 1] = b[i];
        }
        
        for (int j = 0; j < n; ++j) D[m][j] = -c[j];
        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;
        swap(B[r], N[s]);
    }

    bool bland_simplex(int phase) {
        int x = phase == 1 ? m + 1 : m;
        while (true) {
            int s = -1;
            for (int j = 0; j <= n; ++j) {
                if (N[j] == -1) continue;
                if (D[x][j] < -EPS && (s == -1 || N[j] < N[s])) s = j;
            }
            if (D[x][s] > -EPS) return true;
            int r = -1;
            for (int i = 0; i < m; ++i) {
                if (D[i][s] > EPS && (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(VD &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 (!bland_simplex(1) || D[m + 1][n + 1] < -EPS) return -numeric_limits<double>::infinity();
            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]) s = j;
                    pivot(i, s);
                }
        }
        if (!bland_simplex(2)) return numeric_limits<double>::infinity();
        x = VD(n);
        for (int i = 0; i < m; ++i)
            if (B[i] < n)
                x[B[i]] = D[i][n + 1];
        return D[m][n + 1];
    }
};

int main() {
    // Bài toán với các ràng buộc
    VVD A = {{-1, 2}, {1, -1}, {-2, -1}, {1, 0}, {2, 1}, {1, 1}, {1, 2}, {0, 2}};
    VD b = {-1, 2, -6, 5, 16, 12, 21, 10};
    VD c = {3, 2};
    VD x;

    Simplex simplex(A, b, c);
    double result = simplex.solve(x);

    if (result == numeric_limits<double>::infinity())
        cout << "Không giới hạn\n";
    else if (result == -numeric_limits<double>::infinity())
        cout << "Không khả thi\n";
    else {
        cout << "Giá trị tối ưu: " << result << "\n";
        cout << "Giải pháp: ";
        for (double v : x) cout << v << " ";
        cout << "\n";
    }

    return 0;
}