math/Lagrange.h

• View this file on GitHub
• Last update: 2025-11-18 16:58:39+07:00

Code

typedef vector<ld> vd;
vd interpolate(vd x, vd y, int n) {
  vd res(n), temp(n);
  for (int k = 0; k < n - 1; ++k) {
    for (int i = k + 1; i < n; ++i) {
      y[i] = (y[i] - y[k]) / (x[i] - x[k]);
    }
  };
  ld last = 0;
  temp[0] = 1;
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      res[i] += y[k] * temp[i];
      swap(last, temp[i]);
      temp[i] -= last * x[k];
    }
  }
  return res;
}

#line 1 "math/Lagrange.h"
typedef vector<ld> vd;
vd interpolate(vd x, vd y, int n) {
  vd res(n), temp(n);
  for (int k = 0; k < n - 1; ++k) {
    for (int i = k + 1; i < n; ++i) {
      y[i] = (y[i] - y[k]) / (x[i] - x[k]);
    }
  };
  ld last = 0;
  temp[0] = 1;
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      res[i] += y[k] * temp[i];
      swap(last, temp[i]);
      temp[i] -= last * x[k];
    }
  }
  return res;
}

Back to top page