Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <iostream>
- #include <cmath>
- #include <iomanip>
- #include <vector>
- #include <algorithm>
- #include <stdlib.h>
- #include <queue>
- #include <set>
- using namespace std;
- #define fast ios_base::sync_with_stdio(false); cin.tie(false); cout.tie(false)
- #define mp make_pair
- #define All(x) (x).begin(),(x).end()
- #define f_in(s) freopen(s, "r", stdin)
- #define f_out(s) freopen(s, "w", stdout)
- #define file_on f_in; f_out
- typedef long long ll;
- typedef unsigned long long ull;
- typedef long double ld;
- const int inf = 1e9;
- const double eps = 1e-9;
- const long double pi = acos(-1);
- const int nmax = 2010;
- const int mod = 1440;
- vector <vector <pair<int,int> > > a;
- int n,m;
- pair<int,int> norm(pair<int,int> x)
- {
- int g = __gcd(x.first,x.second);
- x.first /= g;
- x.second /= g;
- if (x.second < 0) x.second *=-1, x.first *=-1;
- return x;
- }
- pair<int,int> operator + (pair<int,int> x, pair<int,int> y) {return norm(make_pair(x.first*y.second + y.first*x.second, x.second * y.second));}
- pair<int,int> operator - (pair<int,int> x, pair<int,int> y) {return norm(make_pair(x.first*y.second - y.first*x.second, x.second * y.second));}
- pair<int,int> operator * (pair<int,int> x, pair<int,int> y) {return norm(make_pair(x.first*y.first, x.second * y.second));}
- pair<int,int> operator / (pair<int,int> x, pair<int,int> y) {return norm(make_pair(x.first*y.second, x.second * y.first));}
- void write(pair<int,int> x) {cout << ' ' << x.first; if (x.second != 1) cout << '/' << x.second;}
- void rec(int x, int y)
- {
- if (x == n || y == m)
- {
- for (int i = x; i < n; i++)
- if (a[i][m].first != 0)
- {
- cout << "No solution" << endl;
- return;
- }
- if (n >= m && a[m-1][m-1].first != 0)
- {
- for (int i = 0; i < m; i++)
- write(a[i][m]);
- return;
- }
- for (int i = 0; i < x; i++)
- {
- for (int j = 0; j <= m; j++)
- write(a[i][j]);
- cout << endl;
- }
- return;
- }
- for (int i = x; i < n && a[x][y].first == 0; i++)
- if (a[i][y].first != 0)
- swap(a[i],a[x]);
- if (a[x][y].first == 0)
- {
- rec(x,y+1);
- return;
- }
- for (int i = y + 1; i <= m; i++)
- a[x][i] = a[x][i] / a[x][y];
- a[x][y] = a[x][y] / a[x][y];
- for (int i = 0; i < n; i++)
- if (a[i][y].first != 0 && i != x)
- {
- pair<int,int> coef = a[i][y];
- for (int j = y; j <= m; j++)
- a[i][j] = a[i][j] - (coef * a[x][j]);
- }
- rec(x+1,y+1);
- }
- int main()
- {
- f_in("linear.in");
- f_out("linear.out");
- cin >> n >> m;
- a.assign(n,vector <pair<int,int> > (m+1));
- for (int i = 0; i < n; i++)
- {
- for (int j = 0; j <= m; j++)
- {
- int x;
- cin >> x;
- pair<int,int> t;
- t.first = x;
- t.second = 1;
- a[i][j] = t;
- }
- }
- rec(0,0);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement