DataStructureAndAlgorithm/2023208/main.cpp

#include <math.h>
#include <stdio.h>
#define EPSILON 1e-6

double A[5051] = {0};
double point_xs[101] = {0};
int valid_point_num = 0;
double t[101] = {0};
int n, m;

double get_num(int row, int col) {
    if (col > row) {
        return 0;
    }
    return A[row * (row + 1) / 2 + col];
}

double set_num(int row, int col, double content) {
    if (col > row) {
        return 0;
    }
    return A[row * (row + 1) / 2 + col] = content;
}

bool compare_double(long double a, long double b) {
    return (a - b > 0 ? a - b : -(a - b)) < EPSILON;
}

double evaluate(double x, int highest) {
    double ans = get_num(highest, highest);
    for (int j = highest - 1; j >= 0; j--) {
        ans *= x - point_xs[j];
        ans += get_num(j, j);
    }
    return ans;
}

double evaluate_2(double x, int highest) {
    double ans = t[highest];
    for (int j = highest - 1; j >= 0; j--) {
        ans *= x - point_xs[j];
        ans += t[j];
    }
    return ans;
}

int display_mat() {
    for (int i = 0; i < valid_point_num; i++) {
        for (int j = 0; j < valid_point_num; j++) {
            printf("%lf ", get_num(i, j));
        }
        printf("\n");
    }
    printf("\n");
    return 0;
}

int main_2() {
    double read_x, read_y;
    bool found_duplicate = false;
    for (int i = 0; i < n; i++) {
        scanf("%lf %lf", &read_x, &read_y);
        for (int j = 0; j < valid_point_num; j++) {
            if (compare_double(read_x, point_xs[valid_point_num])) {
                found_duplicate = true;
                break;
            }
        }

        if (!found_duplicate) {
            point_xs[valid_point_num] = read_x;
            t[valid_point_num] = read_y;
            valid_point_num++;
        }
    }

    // Prepare the matrix
    for (int row = 0; row < valid_point_num; row++) {
        set_num(row, 0, 1);
        for (int col = 1; col <= row; col++) {
            set_num(row, col, get_num(row, col - 1) * (point_xs[row] - point_xs[col - 1]));
        }
    }

    // Solve for t
    for (int row = 0; row < valid_point_num; row++) {
        for (int i = 0; i < row; i++) {
            t[row] -= t[i] * get_num(row, i);
        }
        if (!compare_double(t[row], 0)) {
            t[row] /= get_num(row, row);
        }
        else {
            t[row] = 0;
        }
    }

    // Find for highest exponent
    int highest = valid_point_num - 1;
    for (; highest >= 0; highest--) {
        if (!compare_double(t[highest], 0)) {
            break;
        }
    }

    printf("%d\n", highest);

    // Evaluate
    for (int i = 0; i < m; i++) {
        double to_be_evaled = 0;
        scanf("%lf", &to_be_evaled);
        printf("%lf\n", evaluate_2(to_be_evaled, highest));
    }
    return 0;
}

int main_1() {
    for (int i = 0; i < n; i++) {
        bool found_duplicate = false;
        double read_x, read_y;
        scanf("%lf %lf", &read_x, &read_y);
        for (int j = 0; j < valid_point_num; j++) {
            if (compare_double(read_x, point_xs[j])) {
                found_duplicate = true;
                break;
            }
        }

        if (!found_duplicate) {
            point_xs[valid_point_num] = read_x;
            set_num(valid_point_num, 0, read_y);
            valid_point_num++;
        }
    }

    // Go create the full table
    for (int col = 1; col < valid_point_num; col++) {
        int delta = col;
        for (int row = col; row < valid_point_num; row++) {
            set_num(row, col,
                    (get_num(row, col - 1) - get_num(row - 1, col - 1)) /
                        (point_xs[row] - point_xs[row - delta]));
        }
        if (compare_double(get_num(col, col) / 1000, 0)) {
            set_num(col, col, 0);
        }
        // display_mat();
    }

    // Find the highest
    int highest = valid_point_num - 1;
    for (; highest >= 0; highest--) {
        if (compare_double(get_num(highest, highest) / 1000, 0)) {
            continue;
        }
        break;
    }

    printf("%d\n", highest);

    double to_be_evaled = 0;
    for (int i = 0; i < m; i++) {
        scanf("%lf", &to_be_evaled);
        printf("%lf\n", evaluate(to_be_evaled, highest));
    }

    return 0;
}

int main() {
    scanf("%d %d", &n, &m);
    if (n > 50) {
        main_2();
    }
    else {
        main_1();
    }
    return 0;
}