// This code computes an optimal triangulation of a convex polygon.
// The polygon nodes should be listed in the main() method in a cyclic order
// (clockwise or counterclockwise, does not matter).
// 1. Save the code in file PolyTriang.java
// 2. Compile the code with instruction javac PolyTriang.java
// 3. Run it with instruction java PolyTriang

import java.awt.Point;
import java.text.DecimalFormat;

public class PolyTriang
{
  public static double[][] w;      // storage for the triangulation weights
  public static int[][] s;         // storage for the triangulation

  public static void main(String[] args)
  {
    Point[] p = getPoints(args);
    int n = p.length-1;            // # of polygon nodes
 
    MCO(p);
    System.out.println("Table of w[i][j]:");
       System.out.print("j\\i|");
       for (int i=1; i<=n; i++)
         System.out.printf("%7d ", i);
       System.out.print("\n---+");
       for (int i=1; i<=8*n-1; i++)
         System.out.print("-");
       System.out.println();
       for (int j=n; j>=1; j--)
       {
         System.out.print(" " + j + " |");
         for (int i=1; i<=j; i++)
           System.out.printf("%7.3f ", w[i][j]);
         System.out.println();
       }
    System.out.printf("Min weight of triangulation: %.3f\n", w[1][n]);
    System.out.println("\nTable of s[i][j]:");
       System.out.print("j\\i|");
       for (int i=1; i<=n; i++)
         System.out.printf("%2d ", i);
       System.out.print("\n---+");
       for (int i=1; i<=3*n-1; i++)
         System.out.print("-");
       System.out.println();
       for (int j=n; j>=2; j--)
       {
         System.out.print(" " + j + " |");
         for (int i=1; i<=j-1; i++)
           System.out.printf("%2d ", s[i][j]);
         System.out.println();
       }
    System.out.println("\nOptimal triangulation: ");
    MCM(s, 1, n);
  }

  // the bottom-top implementation of the dynamic programming method
  // this algorithm is practically identical to the one for the matrix chain
  public static void MCO(Point[] p)
  {
    int n = p.length-1;       // # of polygon nodes
    w = new double[n+1][n+1]; // create and automatically initialize array w
    s = new int[n+1][n+1];

    for (int l=2; l<=n; l++)
    {
      for (int i=1; i<=n-l+1; i++)
      {
        int j=i+l-1;  
        w[i][j] = Double.MAX_VALUE;
        
        for (int k=i; k<=j-1; k++)
        {
          double q = w[i][k] + w[k+1][j] + W(p[i-1],p[k],p[j]);
          if (q < w[i][j])
          {
            w[i][j] = q;
            s[i][j] = k;
          }
        }
      }
    }
  }

  // algorithm for printing out the chords in an optimal triangulation
  // this algorithm is slightly different from the matrix context
  public static void MCM(int[][] s, int i, int j)
  {
    if (j-i <= 1) return;
    int i1 = i-1;
    if (s[i][j]-i1 > 1) System.out.println("Chord V_" + i1 + " - V_" + s[i][j]);
    if (j-s[i][j] > 1) System.out.println("Chord V_" + s[i][j] + " - V_" + j);
    MCM(s, i, s[i][j]);
    MCM(s, s[i][j]+1, j);
  }

  // this method returns the weight of a triangle
  public static double W(Point i, Point k, Point j)
  {
    double d1 = Math.sqrt((i.x - k.x)*(i.x - k.x) + (i.y - k.y)*(i.y - k.y));
    double d2 = Math.sqrt((i.x - j.x)*(i.x - j.x) + (i.y - j.y)*(i.y - j.y));
    double d3 = Math.sqrt((k.x - j.x)*(k.x - j.x) + (k.y - j.y)*(k.y - j.y));
    return(d1 + d2 + d3);
  }

  public static Point[] getPoints(String[] args)
  {
    if (args.length == 0)
    {
      System.out.println("No input");
      System.exit(0);
    }

    if (args.length%2 != 0)
    {
      System.out.println("Different number of x- and y-coordinates");
      System.exit(0);
    }

    Point[] pts = new Point[args.length/2];
    for (int i=0; i<args.length; i+=2)
    {
      try
      {
        int x = Integer.parseInt(args[i]);
        int y = Integer.parseInt(args[i+1]);
        pts[i/2] = new Point(x, y);
      }
      catch(NumberFormatException e)
      {
        System.out.println("Invalid coordinates of point #" + (i/2));
        System.exit(0);
      }
    }
    return(pts);
  }
}