#include <stdio.h>
#include <stdlib.h>
#include <math.h>

void print_error(int x)
{
    printf("The system does not have a unique solution because the diagonal element from line %d is null", x);
}

int main()
{
    int n, i;
    float z, x[100], f[100], h[100], a[100], b[100], c[100], t[100], s[100], u[100];
    printf("n=> ");
    scanf("%d", &n);
    for (i = 0; i <= n; i++)
    {
        printf("x[%d]=> ", i);
        scanf("%f", &x[i]);
    }
    for (i = 0; i <= n; i++)
    {
        printf("f[%d]=> ", i);
        scanf("%f", &f[i]);
    }
    printf("z=> ");
    scanf("%f", &z);
    for (i = 1; i <= n; i++)
    {
        h[i] = x[i] - x[i - 1];
    }
    for (i = 1; i <= n-1; i++)
    {
        a[i] = 2*(h[i] + h[i + 1]);
    }
    for (i = 1; i <= n - 2; i++)
    {
        b[i] = h[i + 1];
        c[i] = b[i];
    }
    for (i = 1; i <= n - 1; i++)
    {
        t[i] = 6 * (f[i + 1] - f[i]) / h[i + 1] - 6 * (f[i] - f[i - 1]) / h[i];
    }
    n = n - 1;
    // LR factorization start
    for (i = 1; i <= n - 1; i++)
    {
        if (a[i] == 0)
        {
            print_error(i);
            exit(1);
        }
        c[i] = c[i] / a[i];
        a[i + 1] = a[i + 1] - b[i] * c[i];
    }
    for (i = 2; i <= n; i++)
    {
        t[i] = t[i] - c[i - 1] * t[i - 1];
        if (a[n] == 0)
        {
            print_error(n);
            exit(1);
        }
    }
    t[n] = t[n] / a[n];
    for (i = n - 1; i >= 1; i--)
    {
        t[i] = (t[i] - b[i] * t[i + 1]) / a[i];
    }
    // LR factorization end
    for (i = 1; i <= n; i++)
        printf("%f ", t[i]);
    printf("\n");
    n = n + 1;
    u[0] = u[n] = 0;
    for (i = 1; i <= n - 1; i++)
        u[i] = t[i];
    for (i = 1; i <= n; i++)
    {
        if (z > x[i - 1] && z < x[i])
        {
            float temp = (u[i] * powf((z - x[i - 1]), 3) + u[i - 1] * powf(x[i] - z, 3)) / (6 * h[i]) + (f[i] - u[i] * powf(h[i], 2) / 6) * (z - x[i - 1] / h[i]) + (f[i - 1] - u[i - 1] * powf(h[i], 2) / 6) * (x[i] - z / h[i]);
            printf("%f ", temp);
        }
    }

    system("pause");
    return 0;
}