My judge solution to Goat Ropes from UChicago's 2013 Invitational Contest.

goat.cpp

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

#define MAXVAR 50
#define MAXCONSTRAINT 25*49
#define lptype double
#define EPS 1e-7

//Simplex input
//  Maximizes CX subject to AX <= B with X >= 0
lptype C[MAXVAR];
lptype A[MAXCONSTRAINT][MAXVAR];
lptype B[MAXCONSTRAINT];

//simplex temporaries
lptype tableau[MAXCONSTRAINT + 1][MAXVAR + MAXCONSTRAINT + 2];

//Returns CX
lptype simplex(int variables, int constraints) {
	//Initialize tablueau
	int rows = constraints;			//Note rows and cols doesn't count the outermost row/col for convenience
	int cols = variables + constraints + 1;
	for(int i = 0; i < constraints; i++) {
		for(int j = 0; j < variables; j++) tableau[i][j] = A[i][j];
		for(int j = 0; j < constraints; j++) tableau[i][j + variables] = i == j ? 1 : 0;
		tableau[i][variables + constraints] = 0;
		tableau[i][variables + constraints + 1] = B[i];
	}
  for(int j = 0; j < variables; j++)
    tableau[constraints][j] = C[j] == 0 ? 0 : -C[j];
  for(int j = 0; j < constraints; j++)
    tableau[constraints][j + variables] = 0;
	tableau[constraints][variables + constraints] = 1;
	tableau[constraints][variables + constraints + 1] = 0;

	//Pivot until done
	while(true) {
		//Select pivot column
		int pivot_col = 0;
		for(int i = 1; i < cols; i++)
			if(tableau[rows][i] < tableau[rows][pivot_col])
				pivot_col = i;

		//Check for finishing condition
		if(tableau[rows][pivot_col] >= 0) break;

		//Select pivot row
		int pivot_row = 0;
		for(int i = 1; i < rows; i++)
			if(tableau[i][pivot_col] >= EPS)
				if(tableau[pivot_row][pivot_col] < EPS || tableau[i][cols] / tableau[i][pivot_col] < tableau[pivot_row][cols] / tableau[pivot_row][pivot_col])
					pivot_row = i;

		//Perform pivot
		for(int i = 0; i <= rows; i++) {
			if(i == pivot_row) continue;
			lptype ratio = tableau[i][pivot_col] / tableau[pivot_row][pivot_col];
			for(int j = 0; j <= cols; j++)
				tableau[i][j] -= ratio * tableau[pivot_row][j];
			tableau[i][pivot_col] = 0; //should already be zero, just to keep things precise
		}

		//Normalize table
		for(int i = 0; i <= rows; i++) {
			double mx = 0;
			for(int j = 0; j <= cols; j++) {
				mx = max(mx, fabs(tableau[i][j]));
      }
			for(int j = 0; j <= cols; j++) {
				tableau[i][j] /= mx;
      }
		}
	}

	return tableau[rows][cols] / tableau[rows][cols - 1];
}

double XC[MAXVAR];
double YC[MAXVAR];

int main() {
  for(int t = 1; ; t++) {
    memset(A, 0, sizeof(A));
    memset(B, 0, sizeof(B));
    memset(C, 0, sizeof(C));

    int N; cin >> N;
    if(!N) break;

    int p = 0;
    for(int i = 0; i < N; i++) {
      C[i] = 1;
      cin >> XC[i] >> YC[i];
      for(int j = 0; j < i; j++) {
        A[p][i] = 1;
        A[p][j] = 1;
        B[p++] = sqrt((XC[i] - XC[j]) * (XC[i] - XC[j]) +
                      (YC[i] - YC[j]) * (YC[i] - YC[j]));
      }
    }

    printf("%.2f\n", simplex(N, p));
  }
  return 0;
}