import java.io.*; import java.util.*; /** * Solution to Goat Ropes. * * @author vanb */ public class goatropes_vanb { public Scanner sc; public PrintStream ps; /** A list of all X coordinates */ public double xs[]; /** A list of all Y coordinates */ public double ys[]; public static final double epsilon = 0.000001; /** * Distance between posts i and j * * @param i A post number * @param j Another post number * @return The distance between posts i and j */ public double distance( int i, int j ) { return Math.hypot( ys[j] - ys[i], xs[j] - xs[i] ); } /** * Driver * @throws Exception */ public void doit() throws Exception { sc = new Scanner (System.in); ps = System.out; for(;;) { int n = sc.nextInt(); if( n==0 ) break; xs = new double[n]; ys = new double[n]; for( int i=0; i=0, and that setting all Xi's = 0 // forms a Basic Feasible Solution. // k is the number of constraints - those are the Xi+Xj<=Dij inequalities. int k = n*(n-1)/2; // Now, create the Simplex matrix. // There are 1+k rows - one for the objective function, and k for the constraints. // There are 1+n+k columns - one for the values, n for the Xi's, and k for the slack variables // associated with the constraints. double m[][] = new double[1+k][1+n+k]; // We'll use the first row (that's row 0) for the objective function // and the remaining k rows for the constraints. // For convenience, we'll use the first column (which is column 0) for the values, // then columns 1 to n will be the Xi's, and the slack variables will be last. // Start by filling in the objective function. Arrays.fill( m[0], 0.0 ); for( int j=1; j<=n; j++ ) { m[0][j] = -1.0; } // Now, the constraints int row = 0; int slack = n; for( int i=0; iepsilon ) { double value = m[i][0]/m[i][pivotcol]; if( value