Cod sursa(job #2900276)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 10 mai 2022 17:58:57
Problema Algoritmul lui Gauss Scor 80
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.13 kb

/// always:
#include <cstdio>
#include <string>

/// optional:
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <set>

bool home = 1;
using namespace std;

typedef long double ld;
const string TASKNAME="gauss";

const int N=300+7;
const ld INF=(ld)1e18;
const ld eps=(ld)1e-14;
int n;
int m;
ld a[N][N];
int invi[N];
int invj[N];
ld sol[N];

void print() {
  return;
  for (int i=1;i<=n;i++) {
    for (int j=1;j<=m+1;j++) {
      cout<<fixed<<setprecision(6)<<a[i][j]<<" ";
    }
    cout<<"\n";
  }
  cout<<"#########################\n";
}

signed main() {
#ifdef INFOARENA
  home = 0;
#endif

  if(!home) {
    freopen((TASKNAME + ".in").c_str(), "r", stdin);
    freopen((TASKNAME + ".out").c_str(), "w", stdout);
  }else{
    freopen ("I_am_iron_man", "r", stdin);
  }

  cin>>n>>m;
  for (int i=1;i<=n;i++) {
    for (int j=1;j<=m+1;j++) {
      cin>>a[i][j];
    }
  }

  print();

  while (1) {
    ld mx=-INF;
    int r=-1,c=-1;
    for (int i=1;i<=n;i++) {
      if (invi[i]==0) {
        for (int j=1;j<=m;j++) {
          if (invj[j]==0) {
            ld bs=abs(a[i][j]);
            if (bs>eps) {
              if(bs>mx){
                mx=bs;
                r=i;
                c=j;
              }
            }
          }
        }
      }
    }

    if(r==-1) break;

    assert(r!=-1);
    assert(c!=-1);
    ///cout<<r<<" and "<<c<<"\n";
    invi[r]=c;
    invj[c]=r;
    ld dv=a[r][c];
    for (int j=1;j<=m+1;j++) {
      a[r][j]/=dv;
    }
    for (int i=1;i<=n;i++) {
      if (i==r) continue;
      ld ml=a[i][c];
      for (int j=1;j<=m+1;j++) {
        a[i][j]-=a[r][j]*ml;
      }
    }

  }
  print();
  for (int i=1;i<=n;i++) {
    sol[invi[i]]=a[i][m+1];
  }
  for (int i=1;i<=n;i++) {
    for (int j=1;j<=m;j++) {
      a[i][m+1]-=a[i][j]*sol[j];
    }
    if (abs(a[i][m+1])>eps) {
      cout<<"Imposibil\n";
      exit(0);
    }
  }

  for (int i=1;i<=m;i++) {
    cout<<fixed<<setprecision(10)<<sol[i]<<" ";
  }
  cout<<"\n";

}