Advertisement
Guest User

Untitled

a guest
Feb 17th, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.01 KB | None | 0 0
  1. #include <cstdio>
  2. #include <iostream>
  3. #include <cmath>
  4. #include <iomanip>
  5. #include <vector>
  6. #include <algorithm>
  7. #include <stdlib.h>
  8. #include <queue>
  9. #include <set>
  10.  
  11. using namespace std;
  12.  
  13. #define fast ios_base::sync_with_stdio(false); cin.tie(false); cout.tie(false)
  14.  
  15. #define mp make_pair
  16. #define All(x) (x).begin(),(x).end()
  17. #define f_in(s) freopen(s, "r", stdin)
  18. #define f_out(s) freopen(s, "w", stdout)
  19. #define file_on f_in; f_out
  20.  
  21. typedef long long ll;
  22. typedef unsigned long long ull;
  23. typedef long double ld;
  24.  
  25. const int inf = 1e9;
  26. const double eps = 1e-9;
  27. const long double pi = acos(-1);
  28. const int nmax = 2010;
  29. const int mod = 1440;
  30.  
  31. vector <vector <pair<int,int> > > a;
  32. int n,m;
  33.  
  34. pair<int,int> norm(pair<int,int> x)
  35. {
  36. int g = __gcd(x.first,x.second);
  37. x.first /= g;
  38. x.second /= g;
  39. if (x.second < 0) x.second *=-1, x.first *=-1;
  40. return x;
  41. }
  42.  
  43. 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));}
  44. 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));}
  45. pair<int,int> operator * (pair<int,int> x, pair<int,int> y) {return norm(make_pair(x.first*y.first, x.second * y.second));}
  46. pair<int,int> operator / (pair<int,int> x, pair<int,int> y) {return norm(make_pair(x.first*y.second, x.second * y.first));}
  47. void write(pair<int,int> x) {cout << ' ' << x.first; if (x.second != 1) cout << '/' << x.second;}
  48.  
  49. void rec(int x, int y)
  50. {
  51. if (x == n || y == m)
  52. {
  53. for (int i = x; i < n; i++)
  54. if (a[i][m].first != 0)
  55. {
  56. cout << "No solution" << endl;
  57. return;
  58. }
  59. if (n >= m && a[m-1][m-1].first != 0)
  60. {
  61. for (int i = 0; i < m; i++)
  62. write(a[i][m]);
  63. return;
  64. }
  65. for (int i = 0; i < x; i++)
  66. {
  67. for (int j = 0; j <= m; j++)
  68. write(a[i][j]);
  69. cout << endl;
  70. }
  71. return;
  72. }
  73. for (int i = x; i < n && a[x][y].first == 0; i++)
  74. if (a[i][y].first != 0)
  75. swap(a[i],a[x]);
  76. if (a[x][y].first == 0)
  77. {
  78. rec(x,y+1);
  79. return;
  80. }
  81. for (int i = y + 1; i <= m; i++)
  82. a[x][i] = a[x][i] / a[x][y];
  83. a[x][y] = a[x][y] / a[x][y];
  84. for (int i = 0; i < n; i++)
  85. if (a[i][y].first != 0 && i != x)
  86. {
  87. pair<int,int> coef = a[i][y];
  88. for (int j = y; j <= m; j++)
  89. a[i][j] = a[i][j] - (coef * a[x][j]);
  90. }
  91. rec(x+1,y+1);
  92. }
  93.  
  94. int main()
  95. {
  96. f_in("linear.in");
  97. f_out("linear.out");
  98. cin >> n >> m;
  99. a.assign(n,vector <pair<int,int> > (m+1));
  100. for (int i = 0; i < n; i++)
  101. {
  102. for (int j = 0; j <= m; j++)
  103. {
  104. int x;
  105. cin >> x;
  106. pair<int,int> t;
  107. t.first = x;
  108. t.second = 1;
  109. a[i][j] = t;
  110. }
  111. }
  112. rec(0,0);
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement