// Arup Guha
// 2/15/2012
// Calculates the Natural Cubic Spline - Input from a file.
#include <stdio.h>

#define MAX 1000

struct pt {
    double x;
    double y;
};

struct cubic {
    double a;
    double b;
    double c;
    double d;
};


void make_spline(struct pt my_pts[], struct cubic my_spl[], int n);

int main() {

    // Open the input file.
    FILE* ifp = fopen("splines.txt","r");
    int numsplines;
    fscanf(ifp,"%d", &numsplines);

    // Go through each test case.
    int loop;
    for (loop=1; loop<=numsplines; loop++) {

        // Get the number of points.
        int numpoints;
        fscanf(ifp,"%d", &numpoints);
        int numcurves = numpoints - 1;

        struct pt my_points[MAX];
        struct cubic my_splines[MAX];

        // Read in the points.
        int i;
        for (i=0; i<numpoints; i++) {
            fscanf(ifp,"%lf%lf", &my_points[i].x, &my_points[i].y);
        }

        // Make the spline and output the coefficients of each curve.
        make_spline(my_points, my_splines, numcurves);
        printf("\n");

    }

    fclose(ifp);

    return 0;
}

void make_spline(struct pt my_pts[], struct cubic my_spl[], int n) {

    // Fill in a's
    int i;
    for (i=0; i<=n; i++)
        my_spl[i].a = my_pts[i].y;

    // Assuming MAX >= n
    double h[MAX];
    for (i=0; i<n; i++)
        h[i] = my_pts[i+1].x - my_pts[i].x;

    // Calculate alphas.
    double alpha[MAX];
    alpha[0] = 0;
    for (i=1; i<n; i++)
        alpha[i] = 3/h[i]*(my_spl[i+1].a-my_spl[i].a) -
                   3/h[i-1]*(my_spl[i].a-my_spl[i-1].a);

    double L[MAX];
    double mu[MAX];
    double Z[MAX];

    // Set up our initial values.
    L[0] = 1;
    mu[0] = 0;
    Z[0] = 0;

    // Iterate to calculate these auxiliary values.
    for (i=1; i<n; i++) {
        L[i] = 2*(my_pts[i+1].x - my_pts[i-1].x) - h[i-1]*mu[i-1];
        mu[i] = h[i]/L[i];
        Z[i] = (alpha[i] - h[i-1]*Z[i-1])/L[i];
    }

    // Step 5 initial values to back substitite for b, c and d.
    L[n] = 1;
    Z[n] = 0;
    my_spl[n].c = 0;

    // Run through the back substitution.
    for (i=n-1; i>=0; i--) {
        my_spl[i].c = Z[i] - mu[i]*my_spl[i+1].c;
        my_spl[i].b = (my_spl[i+1].a-my_spl[i].a)/h[i] -
                      h[i]*(my_spl[i+1].c+2*my_spl[i].c)/3;
        my_spl[i].d = (my_spl[i+1].c-my_spl[i].c)/(3*h[i]);
    }

    // Basic output of coefficients.
    for (i=0; i<n; i++)
        printf("%.2lf\t%.2lf\t%.2lf\t%.2lf\n", my_spl[i].a, my_spl[i].b,my_spl[i].c,my_spl[i].d );
}