//<pre>
// JAVA SOURCE CODE FOR THE LADYBUG GAME

import java.awt.*;

public class ladybug extends BufferedApplet
{
   public String Copyright_Notice = "LADYBUG GAME. COPYRIGHT 2001 KEN PERLIN";

///// SIZES

   int width=0;                   // THE WIDTH OF THE JAVA APPLET WINDOW
   int w;                         // THE WIDTH OF ONE SQUARE TILE
   Font font = new Font("Helvetica",Font.BOLD, 30); // TEXT FONT FOR MESSAGES

///// COLORS

   int bgR = 160, bgG = 112, bgB = 80; // RED,GREEN,BLUE OF THE BACKGROUND COLOR

   Color bgColor = new Color(bgR,bgG,bgB);    // COLOR FOR UNLIT TILES
   Color darkRed = new Color(160,0,0);        // DARK COLOR FOR LADYBUG BODY
   Color lightRed = new Color(255,200,200);   // HIGHLITE COLOR FOR LADYBUG BODY
   Color lightBlack = new Color(200,200,200); // HILITE COLOR FOR LADYBUG HEAD
   Color eyeColor = new Color(255,255,255);   // LADYBUG'S EYE COLOR
   Color shade[];                             // THE SHADES A TILE CAN HAVE

///// THE STATE OF THE BOARD

   int u=3, v=3;                  // THE LOCATION OF THE CURRENTLY BLANK SQUARE
   int Tile[][] = new int[4][4];  // WHICH TILE IS AT LOCATION U,V
   boolean allVisited = false;    // WHETHER PLAYER HAS WON THE GAME
   long startTime = 0, prevTime;  // CLOCK TIME

///// STATE OF THE LADYBUG

   boolean visited[] = new boolean[15];       // HAS LADYBUG VISITED THIS TILE?

   int mu=0,mv=2;                 // WHICH TILE IS LADYBUG ON (CURRENT TILE)?
   int mk=1;                      // WHICH CURVE OF CURRENT TILE IS LADYBUG ON?
   int nShades=10;                // HOW LONG IT TAKES TO LIGHT UP CURRENT TILE
   int brightness=nShades;        // HOW MUCH CURRENT TILE IS ALREADY LIT UP
   int nSteps=20;                 // TOTAL NUMBER OF STEPS ALONG CURRENT CURVE
   int step=0;                    // HOW FAR LADYBUG IS ALONG CURRENT CURVE
   boolean md = true;             // IS LADYBUG GOING FORWARD OR BACK ON CURVE?

///// ALL THE DATA TO DESCRIBE THE CURVED TRACKS

   /*
     Each tile has 8 "terminals" around its perimeter where curves can
     connect with the outside world (two terminals along each of the four
     sides of the tile).  We number them clockwise from left, as follows:

                             --1--2--
                             0      3
                             |      | 
                             7      4
                             --6--5--
   */

   final int LT = 0; // LEFT   EDGE, TOP    TERMINAL
   final int TL = 1; // TOP    EDGE, LEFT   TERMINAL
   final int TR = 2; // TOP    EDGE, RIGHT  TERMINAL
   final int RT = 3; // RIGHT  EDGE, TOP    TERMINAL
   final int RB = 4; // RIGHT  EDGE, BOTTOM TERMINAL
   final int BR = 5; // BOTTOM EDGE, RIGHT  TERMINAL
   final int BL = 6; // BOTTOM EDGE, LEFT   TERMINAL
   final int LB = 7; // LEFT   EDGE, BOTTOM TERMINAL

   // To get from each of the eight terminals to its opposing terminal:

   // Opposing:  0  1  2  3  4  5  6  7

   int opp[] = { 3, 6, 5, 0, 7, 2, 1, 4 };

   /*
     The Shapes array describes the curve-shapes used make the curved tracks
     on the tiles.  There are six shapes, each of which is specified as a
     set of key points.

     For each curve, we specify two sets of numbers.  The first set of numbers
     specifies the x coordinates of the key points, and the second set of
     numbers specifies the y coordinates of the key points.
   */

   double Shapes[][][] = {
      {{0,.1,.23,.3,.3},      {.3,.3,.23,.1,0}},
      {{0,.3,.6,.7,.7},       {.3,.3,.19,.02,0}},
      {{0,.3,.7,1},           {.3,.3,.3,.3}},
      {{0,.15,.4,.6,.85,1.},  {.3,.3,.42,.58,.7,.7}},
      {{0.,.27,.57,.7,.7},    {.3,.3,.43,.73,1.}},
      {{0,.07,.22,.22,.07,0}, {.3,.3,.45,.55,.7,.7}},
   };

   /*
     Each curve connects one of the eight terminals to one other terminal.
     This means there can be at most 8 x 8 possible curves.

     Actually, there are fewer, since you can't connect a terminal to
     itself inside a tile - only with one of the other seven terminals.

     The Curves array defines the curve used to connect any two terminals.
     That's why it has 8x8 = 64 entries.

     Each entry is made by starting with one of the shapes from the Shapes
     array above, and then doing some combination of flips on that curve
     shape (horizontal, vertical or diagonal).  The first argument to function
     p tells which of the curves to use from the Shapes array; the second
     argument is a bit mask that specifies the combination of flips to do.
   */

   double Curves[][][] = {
   // LT      TL      TR      RT      RB      BR      BL      LB 
      p(0,0), p(0,0), p(1,0), p(2,0), p(3,0), p(4,0), p(1,5), p(5,0), // LT
      p(0,0), p(0,0), p(5,4), p(1,1), p(4,4), p(3,4), p(2,4), p(1,4), // TL

      p(1,0), p(5,4), p(0,0), p(0,1), p(1,6), p(2,6), p(3,6), p(4,6), // TR
      p(2,0), p(1,1), p(0,1), p(0,0), p(5,1), p(1,7), p(4,1), p(3,1), // RT

      p(3,0), p(4,4), p(1,6), p(5,1), p(0,0), p(0,3), p(1,3), p(2,2), // RB
      p(4,0), p(3,4), p(2,6), p(1,7), p(0,3), p(0,0), p(5,5), p(1,2), // BR

      p(1,5), p(2,4), p(3,6), p(4,1), p(1,3), p(5,5), p(0,0), p(0,2), // BL
      p(5,0), p(1,4), p(4,6), p(3,1), p(2,2), p(1,2), p(0,2), p(0,0), // LB
   };

   /*
     The CurveSet array describes the set of curves to draw onto each of the
     fifteen tiles.  There are four values for each entry, because four curves
     are drawn onto each tile.

     Values are specified in base 8 (when you start a number with the "0"
     digit, Java interprets it as base 8).  In effect, the second and third
     digit of each value in CurveSet specifies a row and column into the
     Curves array, which gives the starting and ending terminal for that curve.
   */

   int CurveSet[][] = {

        {001,023,046,057}, // CURVE SET FOR TILE 0
        {001,027,035,046}, // CURVE SET FOR TILE 1, ETC.
        {002,014,037,056},
        {004,012,037,056},
        {001,024,036,057},

        {001,027,036,045},
        {002,015,037,046},
        {006,013,024,057},
        {001,024,037,056},
        {002,013,046,057},

        {002,017,034,056},
        {007,015,026,034},
        {001,027,034,056},
        {002,014,036,057},
        {002,017,035,046},
   };

   /*
     The p function transforms the key points of one of the curve
     shapes described in the Shapes array.  The first argument n, an
     index into the Shapes array, tells which curve shape to use.

     The second argument xform is a bit mask.  The p function flips
     horizontally about the tile center if the 0 bit of xform is set,
     flips vertically about the tile center if the 1 bit of xform is
     set, and flips diagonally about the tile center if the 2 bit of
     xform is set.  By setting various combinations of these three
     bits, you can specify any useful transformation of the original
     curve.
   */

   double[][] p(int n, int xform) {
      boolean flipX  = (xform & 1) != 0;            // FLIP HORIZONTALLY?
      boolean flipY  = (xform & 2) != 0;            // FLIP VERTICALLY?
      boolean swapXY = (xform & 4) != 0;            // FLIP ALONG DIAGONAL?

      double [][] shape = Shapes[n];

      double [] x = new double[shape[0].length];
      double [] y = new double[shape[1].length];

      for (int i = 0 ; i < x.length ; i++)          // IF HORIZONTAL FLIP
        x[i] = flipX ? 1-shape[0][i] : shape[0][i]; //    REVERSE LEFT/RIGHT
      for (int i = 0 ; i < y.length ; i++)          // IF VERTICAL FLIP
        y[i] = flipY ? 1-shape[1][i] : shape[1][i]; //    REVERSE UP/DOWN

      double dst[][] = new double[2][];
      dst[0] = swapXY ? y : x;                      // IF DIAGONAL FLIP
      dst[1] = swapXY ? x : y;                      //    SWAP X AND Y

      return dst;
   }

// RENDER THE ENTIRE GAME EVERY ANIMATION FRAME

   public void render(Graphics g) {

      //////////// THINGS TO DO WHEN FIRST STARTING UP: //////////////////

      if (width == 0) {

         width = bounds().width;  // REMEMBER HOW WIDE THE APPLET WINDOW IS.
         w = width/4;             // ONE TILE IS 1/4 THE WIDTH OF THE WINDOW.

         // PLACE THE 15 TILES IN THEIR INITIAL POSITIONS.

         for (int u = 0 ; u < 4 ; u++)
         for (int v = 0 ; v < 4 ; v++)
           Tile[u][v] = 4*u + v;

         // REMEMBER WHAT TIME WAS ON THE CLOCK WHEN WE STARTED THE PROGRAM.

         startTime = System.currentTimeMillis();

         // MAKE A GRADATION OF SHADES, SO CURRENT TILE CAN LIGHT UP GRADUALLY
         // AFTER THE LADYBUG HAS ENTERED IT.

         shade = new Color[nShades];
         for (int s = 0 ; s < nShades ; s++) {
            double t = 1+.5*s/(nShades-1);
            shade[s] = new Color((int)(t*bgR),(int)(t*bgG),(int)(t*bgB));
         }
      }
      //////////////////////////////////////////////////////////////////

      // FIND OUT HOW MUCH TIME HAS ELAPSED SINCE PROGRAM STARTED RUNNING.

      long time = System.currentTimeMillis() - startTime;
      if (time - prevTime > 30) {       // EVERY 30 MILLISECONDS WE MUST
         step = (step+1) % nSteps;      // MOVE LADYBUG ALONG CURRENT CURVE.
         prevTime = time;
      }

      // DRAW THE BLANK SQUARE

      g.setColor(bgColor);
      g.fill3DRect(u*w,v*w,w,w, false);

      // DRAW THE 15 TILES

      allVisited = true;
      for (int U = 0 ; U < 4 ; U++)     // LOOP OVER ALL SQUARES
      for (int V = 0 ; V < 4 ; V++) {
         if (U==u && V==v)              // EXCEPT FOR THE BLANK SQUARE.
            continue;
          int tile = Tile[U][V];        // WHICH TILE IS AT THIS SQUARE?
         int r = mu==U && mv==V && brightness < nShades
            ? brightness : visited[tile]
            ? nShades-1 : 0;            // WHAT SHADE IS THE TILE?
          drawTile(g, U,V, tile, r);    // DRAW THE TILE.
         if (! visited[tile])           // IF ANY TILE IS STILL UNVISITED,
            allVisited = false;         // THEN PLAYER HAS NOT YET WON.
      }

      // GRADUALLY BRIGHTEN THE TILE CONTAINING THE LADYBUG,

      int tile = Tile[mu][mv];
      brightness = visited[tile] ? brightness+1 : 0;

      // AND REMEMBER THAT THE LADYBUG HAS VISITED THIS TILE.

      visited[tile] = true;

////////////////// FIGURE OUT WHERE THE LADYBUG IS /////////////////

      // WHICH CURVE IS THE LADYBUG ON?

      int c = CurveSet[tile][mk];

      // HOW FAR HAS THE LADYBUG TRAVELED ALONG THE CURVE?

      double t = (double)step / nSteps;
      t = (md ? t : 1-t);
      if (t < .5)
         t = .5*Math.pow(2*t,.5);
      else
         t = 1-.5*Math.pow(2*(1-t),.5);

      // WHAT ARE THE LADYBUG'S (X,Y) COORDINATES ON THE CURVE?

      double X = evalCurve(t, Curves[c][0]);
      double Y = evalCurve(t, Curves[c][1]);

      // WHAT DIRECTION IS THE LADYBUG HEADING?

      double DX = evalCurve(t+(md?.1:-.1), Curves[c][0]) - X;
      double DY = evalCurve(t+(md?.1:-.1), Curves[c][1]) - Y;
      double R = Math.sqrt(DX*DX+DY*DY);
      double dx = DX*8/R;  // HOW MUCH LEFT OR RIGHT THE LADYBUG FACES
      double dy = DY*8/R;  // HOW MUCH UP OR DOWN THE LADYBUG FACES

////////////////////////// DRAW THE LADYBUG /////////////////////////

      // FIND WHERE TO DRAW THE LADYBUG'S BODY, IN PIXEL COORDINATES

      double x = mu*w + w * X;
      double y = mv*w + w * Y;

      // FIND WHERE TO DRAW THE LADYBUG'S HEAD, IN PIXEL COORDINATES

      double hx = x+dx;
      double hy = y+dy;

      // DRAW THE HEAD

      g.setColor(Color.black);
      fillOval(g, hx-6,hy-6,12,12);

      // DRAW THE EYES

      g.setColor(eyeColor);
      fillOval(g, hx+.3*dx+.6*dy-2.5,hy+.3*dy-.6*dx-2.5,5,5);
      fillOval(g, hx+.3*dx-.6*dy-2.5,hy+.3*dy+.6*dx-2.5,5,5);

      // TRIM A LITTLE FROM THE EYES

      g.setColor(Color.black);
      fillOval(g, hx+.3*dx-5.5,hy+.3*dy-5.5,11,11);

      // DRAW THE HILITE ON THE HEAD

      g.setColor(lightBlack);
      fillOval(g, hx+.3*dx-3.5,hy+.3*dy-5.0,3,3);
      fillOval(g, hx+.3*dx-5.0,hy+.3*dy-3.5,3,3);

      // DRAW THE DARK-SHADED PART OF BODY

      g.setColor(darkRed);
      fillOval(g, x-10,y-10,20,20);

      // DRAW THE BODY

      g.setColor(Color.red);
      fillOval(g, x-10,y-10,17,17);

      // DRAW THE LINE THAT RUNS ALONG THE MIDDLE OF THE BACK

      g.setColor(Color.black);
      drawLine(g, x-dx,y-dy,x+dx,y+dy);

      // DRAW THE SPOTS ON THE BACK

      g.setColor(Color.black);
      fillOval(g, x-.6 *dy+.3*dx-2.5,y+.6 *dx+.3*dy-2.5,5,5);
      fillOval(g, x+.6 *dy+.3*dx-2.5,y-.6 *dx+.3*dy-2.5,5,5);
      fillOval(g, x-.35*dy-.5*dx-2  ,y+.35*dx-.5*dy-2  ,4,4);
      fillOval(g, x+.35*dy-.5*dx-2  ,y-.35*dx-.5*dy-2  ,4,4);

      // DRAW THE HILITE ON THE BODY

      g.setColor(lightRed);
      fillOval(g, x-5,y-8,3,3);
      fillOval(g, x-7,y-7,4,4);
      fillOval(g, x-8,y-5,3,3);

/////////////////////////////////////////////////////////////////////

      // CONGRATULATE THE PLAYER IF GAME HAS BEEN WON:

      if (allVisited) {
         g.setFont(font);
         g.setColor(Color.black);                     // DRAW DROP-SHADOW FIRST
         g.drawString("CONGRATULATIONS!", 24, 44);
         g.drawString("YOU'VE SOLVED IT!!!", 24, 84);
         g.setColor(Color.white);                     // THEN DRAW TEXT ITSELF
         g.drawString("CONGRATULATIONS!", 20, 40);
         g.drawString("YOU'VE SOLVED IT!!!", 20, 80);
      }

//// WHEN THE LADYBUG IS TRAVELLING ACROSS AN EDGE, FROM ONE TILE TO THE NEXT:

      if (step >= nSteps-1) {       // IF THE LADYBUG IS DONE TRAVERSING TILE
         int u0=mu,v0=mv;             // REMEMBER WHICH SQUARE WE WERE ON
         int s = S(X,Y);              // FIND NEAREST TERMINAL
          switch (s) {                // JUMP THRU TERMINAL TO NEXT SQUARE
         case LB: case LT: mu--; break;   // THRU LEFT   EDGE
         case RB: case RT: mu++; break;   // THRU RIGHT  EDGE
         case TL: case TR: mv--; break;   // THRU TOP    EDGE
         case BL: case BR: mv++; break;   // THRU BOTTOM EDGE
         }
         s = opp[s];                  // GO TO OPPOSING TERMINAL IN NEW SQUARE.

         // IF THE LADYBUG HAS HIT A WALL OR THE EMPTY SQUARE, THEN

         if (mv < 0 || mv > 3 || mu < 0 || mu > 3 || mu==u && mv==v) {

            // BOUNCE LADYBUG BACK TO ORIGINAL SQUARE AND CURVE

            mu = u0;                             // RESTORE OLD SQUARE
            mv = v0;
            s = opp[s];                          // RESTORE OLD TERMINAL

            for (tile = 0 ; tile < 15 ; tile++)  // UNLIGHT ALL THE TILES
               visited[tile] = false;            // TO RESTART THE GAME.
         }

         // DON'T LET THE LADYBUG GO OFF THE 4x4 BOARD.

         mu = Math.max(0,Math.min(3,mu));
         mv = Math.max(0,Math.min(3,mv));

         // GIVEN SQUARE'S LOCATION, FIND OUT WHICH TILE THE LADYBUG IS NOW ON.

         tile = Tile[mu][mv];

         // WHICH CURVE ON THE NEW TILE CONTAINS THE TERMINAL THROUGH
         // WHICH THE LADYBUG HAS JUST ENTERED?

         int k = 0;
         for ( ; k < CurveSet[tile].length ; k++) {
            c = CurveSet[tile][k];
            X = evalCurve(0, Curves[c][0]);
            Y = evalCurve(0, Curves[c][1]);
            if (S(X,Y) == s) { // IF TERMINAL IS AT START OF THIS CURVE, THEN
               md = true;      // LADYBUG SHOULD GO FORWARD ALONG THE CURVE.
               mk = k;
               break;
            }
            X = evalCurve(1, Curves[c][0]);
            Y = evalCurve(1, Curves[c][1]);
            if (S(X,Y) == s) { // IF TERMINAL IS AT END OF THIS CURVE, THEN
               md = false;     // LADYBUG SHOULD GO BACKWARD ALONG THE CURVE.
               mk = k;
               break;
            }
         }

         // PLACE THE LADYBUG AT THE BEGINNING OF THIS NEXT CURVE.

         c = CurveSet[tile][mk];
         nSteps = Curves[c][0].length * 5;  // FIVE STEPS FOR EVERY KEY POINT
         if (Curves[c][0][1] == .1)
            nSteps -= 10;                   // BUT LESS FOR VERY SHORT CURVE
         step = 0;
      }
   }

/////// ROUTINES TO SUPPORT DRAWING WITH FLOATING POINT ARGUMENTS /////

   void fillOval(Graphics g, double x, double y, double w, double h) {
      g.fillOval((int)x, (int)y, (int)w, (int)h);
   }

   void drawLine(Graphics g, double ax, double ay, double bx, double by) {
      g.drawLine((int)ax, (int)ay, (int)bx, (int)by);
   }

//////////////////////////////////////////////////////////////////////

   /*
     Figure out which terminal the ladybug is near, depending on whether it's
     on the upper left edge, lower right edge, etc.  The S function figures
     this out from looking at where the ladybug is within the square.
   */

   int S(double X,double Y) {
       return X > .5 ? (Y > .5 ? (Y > .7 ? BR : RB) : (Y < .3 ? TR : RT))
                     : (Y > .5 ? (Y > .7 ? BL : LB) : (Y < .3 ? TL : LT));
   }

   // DRAW ONE TILE AND ALL OF ITS CURVED TRACKS.

   void drawTile(Graphics g, int u, int v, int tile, int r) {

      // DRAW THE BASE TILE COLOR

      g.setColor(shade[r]);
      g.fillRect(u*w,v*w, w, w);

      // DRAW THE CURVES

      g.setColor(Color.black);
         for (int k = 0 ; k < CurveSet[tile].length ; k++) {
            double x0 = 0, y0 = 0;
            for (double t = 0 ; t < 1 ; t += .1) {
               int c = CurveSet[tile][k];
               double x1 = u*w + w * evalCurve(t, Curves[c][0]);
               double y1 = v*w + w * evalCurve(t, Curves[c][1]);
               if (t > 0)
                  drawLine(g, x0, y0, x1, y1);
               x0 = x1;
               y0 = y1;
            }
         }

      // DRAW FAKE 3D EDGES, TO MAKE THE TILE LOOK RAISED.

      g.setColor(shade[r].brighter()); // LIGHTER TOP AND LEFT EDGES
      g.fillRect(u*w,v*w,1,w-1);
      g.fillRect(u*w,v*w,w-1,1);
      g.setColor(Color.gray);          // DARKER BOTTOM AND RIGHT EDGES
      g.fillRect(u*w+w-1,v*w,1,w-1);
      g.fillRect(u*w,v*w+w-1,w-1,1);
   }

   // WHEN PLAYER CLICKS ON A TILE, SWAP IT WITH THE BLANK SQUARE IF POSSIBLE.

   public boolean mouseUp(Event e, int x, int y) {

      // WHICH TILE HAS PLAYER CLICKED ON?

      int U = x/w, V = y/w;

      // IF THE CLICKED-ON IS NEXT TO THE BLANK SQUARE:

      if (U >= 0 && U < 4 && V >= 0 && V < 4 && Math.abs(U-u)+Math.abs(V-v)==1) {

         // IF THE LADYBUG IS ON THE CLICKED-ON TILE, MOVE THE LADYBUG.

         if (mu == U && mv == V) {
            mu = u;
            mv = v;
         }

        // SWAP THE CLICKED-ON TILE WITH THE BLANK SQUARE.

         Tile[u][v] = Tile[U][V];
         u = U;
         v = V;
      }
      allVisited = false; // IN CASE PLAYER HAS JUST WON, RESTART THE GAME.
      return true;
   }

///////// THE REST OF THE CODE IS ALL MATH FOR EVALUATING THE CURVES /////////

   // EVALUATE CURVE AT ONE POINT

   double evalCurve(double x, double F[]) {

      int n = F.length;

      // IF NECESSARY, INITIALIZE ARRAY OF PARAMETER VALUES FOR EVALUATING
      // SPLINE CURVES HAVING THIS NUMBER OF KEY POINTS.

      if (T[n] == null) {
         T[n] = new double[n];
         for (int i = 0 ; i < n ; i++)
            T[n][i] = i / (n - 1.);
      }

      return evalCurve(x, T[n], F);
   }

   double T[][] = new double[10][];

   double evalCurve(double x, double T[], double F[]) {
      int n = T.length;
      double y=0;
      if (n == 0)
         y = .5;
      else if (x < T[0])
         y = F[0];
      else if (x >= T[n-1])
         y = F[n-1];
      else
         for (int i=0 ; i < n-1 ; i++)
            if (x >= T[i] && x < T[i+1]) {
               y = hermite(T[i], T[i+1],
                           F[i], F[i+1],
                           s(i,n,T,F), s(i+1,n,T,F),x);
               break;
            }
      return y;
   }

   // COMPUTE SLOPE AT A KEY POINT

   double s(int i, int n, double T[], double F[]) {
      double s = slopeIsZero(i,n,F) ? 0 :
         ((F[i+1]-F[i  ])/(T[i+1]-T[i  ]) * (T[i  ]-T[i-1]) +
          (F[i  ]-F[i-1])/(T[i  ]-T[i-1]) * (T[i+1]-T[i  ]) )
         / (T[i+1]-T[i-1]);

      s = Math.max(-10,Math.min(10,s));
      if (i > 0 && slopeIsZero(i-1,n,F)) {
         double limit = 2*Math.abs((F[i]-F[i-1]) / (T[i]-T[i-1]));
         s = Math.max(-limit, Math.min(limit, s));
      }
      if (i < n-1 && slopeIsZero(i+1,n,F)) {
         double limit = 2*Math.abs((F[i+1]-F[i]) / (T[i+1]-T[i]));
         s = Math.max(-limit, Math.min(limit, s));
      }
      return s;
   }

   // SLOPE IS ZERO AT ENDS OF CURVE AND AT MINIMA AND MAXIMA

   boolean slopeIsZero(int i, int n, double F[]) {
      return i <= 0 || i >= n-1 || (F[i]-F[i-1])*(F[i]-F[i+1]) >= 0;
   }

   // EVALUATE A HERMITE CUBIC AT ONE DOMAIN POINT

   double hermite(double x0,double x1,
                  double y0,double y1, double s0,double s1, double x) {

      double t = (x - x0) / (x1 - x0);
      double tt = t*t, ttt = t*tt;

      return y0 * (1       - 3*tt + 2*ttt)     +
             s0 * (   + t  - 2*tt +   ttt) / 3 +
             s1 * (        -   tt +   ttt) / 3 +
             y1 * (        + 3*tt - 2*ttt)     ;
   }
}